AN IMPLEMENTATION OF MULTIPLE AND MULTIVARIATE FOURIER-TRANSFORMS ON VECTOR PROCESSORS

Several algorithms for multiple and multivariate complex Fourier transforms are suggested. They use little or no scratch space, i.e., they are essentially in-place. Furthermore, they display high levels of regular parallelism needed for vector-parallel computers. Data access is mainly by stride 1. These algorithms correspond to matrix factorizations using transposition permutations. An essential tool used in defining the permutations and the factorizations are Kronecker products. The suggested algorithms are combined with a method for one-dimensional fast Fourier transforms which is also in-place and accesses data with stride 1. Although the number of floating point operations and the total degree of parallelism is left unchanged by the methods used here, data access is much more regular This is reflected in substantially lower values of anew indicator called loop overhead indicator and often by execution times approximately 2 to 5 times lower, even for moderate problem sizes on the Fujitsu VP 2200, compared to the implementation of the fundamental tenser product factorization.