| 摘要 |
Methods, systems, and articles of manufacture consistent with the present invention compute a multidimensional fast Fourier transform of an original matrix having rows and columns of data. The original matrix is divided into a number of blocks of data, each block including at least one datum, the number of rows of data in each block being less than a total number of rows of data in the original matrix. A one-dimensional partial fast Fourier transform of each block in a row of blocks is computed. A result of the computations is stored in a resultant matrix having rows and columns. The resultant matrix is transposed to a transposed matrix having rows and columns. While transposing the resultant matrix, one-dimensional partial fast Fourier transforms of each block of subsequent rows of blocks are simultaneously computed, one row of blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each block.
|
