Multidimensional chirp algorithms for computing Fourier transforms

This paper derives multidimensional chirp algorithms for computing Fourier transforms. The continuous versions of the algorithms compute the function G(y) = F(My) where F(y) is the Fourier transform of a function f (x) of a vector variable x and M is an invertible matrix. The discrete versions of the algorithms compute values of F over the lattice L-2 = ML1 from values of f over a lattice L-1. In contrast to algorithms based on the discrete Fourier transforra (DFT), L-2 need not contain the lattice reciprocal to L-1. If M is symmetric, the algorithms are multidimensional 'versions of the Bluestein chirp algorithm that employs two point-wise multiplication operations (PMO's) and one convolution operation (CO). The discrete version may be efficiently implemented using fast algorithms to compute the convolutions. If M is not symmetric, three modifications are required. First, the Fourier transform is factored as the product of two Fresnel transforms. Second, the matrix M is factored as M = AB where A and B are symmetric matrices. Third, the Fresnel transforms are modified by the matrices A and B and each modified transform is factored.into a product of two PMO's and one CO.