Computer program for the Fourier transform of data with crystal symmetry

Abstract

Summary form only given. L. Auslander has used algebraic methods to give a mathematical structure to a study of the symmetries of crystals. This has led to a very useful hierarchical classification of all possible symmetries and to an algebraic structure for the discrete Fourier transform of data with crystallographic symmetry. These are designed so as to lead to relations that are potentially useful in designing computational algorithms for computing the Fourier transform. An approach to implementing Auslander's methods that has several important features is described. Only nonredundant data need be stored. Thus, for the case of threefold symmetry, only slightly more than 1/3 of the full set of data need be stored. The problem is broken down into small modules that employ efficient Winograd-type fast Fourier transform algorithms. Most of the calculation is done by calling subroutines which compute smaller conventional 3-D Fourier transforms. This permits the use of efficient available Fourier transform subroutines for the time-consuming parts of the calculations. Indexing and permutations are done on small arrays, thereby reducing data transfer time and storage of index vectors. The method can be implemented on a vector processor. A prototype program was written and tested for a case of 120° rotational symmetry in a 60 by 60 by 60 cube. It was 5.2 times as fast as a conventional 3-D program for the same data.