Patent ID: 7483932

Claim:
A computer-implemented method in a data processing system having a plurality of processors and a program for computing a multidimensional fast Fourier transform of an original matrix having rows and columns of data, the method comprising the steps of: dividing the original matrix 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 first of the plurality of processors locking a row of blocks and computing a one-dimensional partial fast Fourier transform of each block in the row of blocks, a result of the computations being stored in a resultant matrix having rows and columns; a second processor of the plurality of processors transposing the resultant matrix to a transposed matrix having rows and columns, the transposed matrix being a completed multidimensional fast Fourier transform result that is stored in a data structure in a memory of the data processing system; and while transposing the resultant matrix, at least a third processor of the plurality of processors simultaneously computing one-dimensional partial fast Fourier transforms of each block of subsequent rows of blocks, one row of blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each block.