Method and system for computing multidimensional fast Fourier transforms

1. 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.

2. The method of claim 1 , further comprising the steps of:

dividing the transposed matrix into a number of transposed-matrix blocks, each transposed-matrix block including at least one datum, the number of rows in each transposed-matrix block being less than a total number of rows of the transposed matrix;

computing a one-dimensional partial fast Fourier transform of each transposed-matrix block in a row of transposed-matrix blocks, a result of the computations being stored in a second resultant matrix having rows and columns;

transposing the second resultant matrix to a final matrix having rows and columns; and

while transposing the second resultant matrix, simultaneously computing one-dimensional partial fast Fourier transforms of each transposed-matrix block of subsequent rows of transposed-matrix blocks, one row of transposed-matrix blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each transposed-matrix block.

3. The method of claim 2 , wherein the transposed matrix and the second resultant matrix are the same matrix.

4. The method of claim 1 , further comprising the step of:

identifying when the one-dimensional partial fast Fourier transform of each block is completed.

5. The method of claim 1 , further comprising the step of:

identifying when the one-dimensional fast Fourier transform of each transposed-matrix block is completed.

6. The method of claim 1 , wherein the original matrix and the resultant matrix are the same matrix.

7. 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 columns of data in each block being less than a total number of columns of data of the original matrix;

a first of the plurality of processors locking a column of blocks and computing a one-dimensional partial fast Fourier transform of each block in the column 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 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 columns of blocks, one column of blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each block.

8. The method of claim 7 , further comprising the steps of:

dividing the transposed matrix into a number of transposed-matrix blocks, each transposed-matrix block including at least datum, the number of columns in each transposed-matrix block being less than a total number of blocks of the transposed matrix;

computing a one-dimensional partial fast Fourier transform of each transposed-matrix block in a column of transposed-matrix blocks, a result of the computations being stored in a second resultant matrix having rows and columns;

transposing the second resultant matrix to a final matrix having rows and columns; and

while transposing the second resultant matrix, simultaneously computing one-dimensional partial fast Fourier transforms of each transposed-matrix block of subsequent columns of transposed-matrix blocks, one column of transposed-matrix sections at a time, until one-dimensional partial fast Fourier transforms are computed for each transposed-matrix section.

9. The method of claim 8 , wherein the transposed matrix and the second resultant matrix are the same matrix.

10. The method of claim 7 , further comprising the step of:

identifying when the one-dimensional partial fast Fourier transform of each section is completed.

11. The method of claim 7 , further comprising the step of:

identifying when the one-dimensional partial fast Fourier transform of each transposed-matrix section is completed.

12. The method of claim 7 , wherein the original matrix and the resultant matrix are the same matrix.

13. A computer-readable medium containing instructions that cause a data processing system having a plurality of processors and a program to perform a computer-implemented method 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 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 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.

14. The computer-readable medium of claim 13 , further comprising the steps of:

dividing the transposed matrix into a number of transposed-matrix blocks, each transposed-matrix block including at least one datum, the number of rows in each transposed-matrix block being less than a total number of rows of the transposed matrix;

computing a one-dimensional partial fast Fourier transform of each transposed-matrix block in a row of transposed-matrix blocks, a result of the computations being stored in a second resultant matrix having rows and columns;

transposing the second resultant matrix to a final matrix having rows and columns; and

while transposing the second resultant matrix, simultaneously computing one-dimensional partial fast Fourier transforms of each transposed-matrix block of subsequent rows of transposed-matrix blocks, one row of transposed-matrix blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each transposed-matrix block.

15. The computer-readable medium of claim 13 , further comprising the step of:

identifying when the one-dimensional partial fast Fourier transform of each block is completed.

16. The computer-readable medium of claim 13 , further comprising the step of:

identifying when the one-dimensional fast Fourier transform of each transposed-matrix block is completed.

17. The computer-readable medium of claim 13 , wherein the original matrix and the resultant matrix are the same matrix.

18. The computer-readable medium of claim 14 , wherein the transposed matrix and the second resultant matrix are the same matrix.

19. A computer-readable medium containing instructions that cause a data processing system having a plurality of processors and a computer-implemented program to perform a method 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 columns of data in each block being less than a total number of columns of data of the original matrix;

a first processor of the plurality of processors locking a column of blocks and computing a one-dimensional partial fast Fourier transform of each block in the column 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 columns of blocks, one column of blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each block.

20. The computer-readable medium of claim 19 , further comprising the steps of:

dividing the transposed matrix into a number of transposed-matrix blocks, each transposed-matrix block including at least datum, the number of columns in each transposed-matrix block being less than a total number of blocks of the transposed matrix;

computing a one-dimensional partial fast Fourier transform of each transposed-matrix block in a column of transposed-matrix blocks, a result of the computations being stored in a second resultant matrix having rows and columns;

transposing the second resultant matrix to a final matrix having rows and columns; and

while transposing the second resultant matrix, simultaneously computing one-dimensional partial fast Fourier transforms of each transposed-matrix block of subsequent columns of transposed-matrix blocks, one column of transposed-matrix sections at a time, until one-dimensional partial fast Fourier transforms are computed for each transposed-matrix section.

21. The computer-readable medium of claim 20 , wherein the transposed matrix and the second resultant matrix are the same matrix.

22. The computer-readable medium of claim 19 , further comprising the step of:

identifying when the one-dimensional partial fast Fourier transform of each section is completed.

23. The computer-readable medium of claim 19 , further comprising the step of:

identifying when the one-dimensional partial fast Fourier transform of each transposed-matrix section is completed.

24. The computer-readable medium of claim 19 , wherein the original matrix and the resultant matrix are the same matrix.

25. A computer-implemented data processing system for computing a multidimensional fast Fourier transform of an original matrix having rows and columns of data, the data processing system comprising:

a plurality of processing units; and

a memory comprising a program that:

divides the original matrix into a number of blocks of data, each block including at least one datum, the number of columns of data in each block being less than a total number of columns of data of the original matrix;

on a first processing unit of the plurality of processing units, locks a column of blocks and computes a one-dimensional partial fast Fourier transform of each block in the column of blocks, a result of the computations being stored in a resultant matrix having rows and columns;

on a second processing unit, transposes 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, on at least a third processing unit of the plurality of processing units, simultaneously computes one-dimensional partial fast Fourier transforms of each block of subsequent columns of blocks, one column of blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each block.

26. The data processing system of claim 25 , wherein the program divides the transposed matrix into a number of transposed-matrix blocks, each transposed-matrix block including at least one datum, the number of rows in each transposed-matrix block being less than a total number of rows of the transposed matrix;

computes a one-dimensional partial fast Fourier transform of each transposed-matrix block in a row of transposed-matrix blocks, a result of the computations being stored in a second resultant matrix having rows and columns;

transposes the second resultant matrix to a final matrix having rows and columns; and

while transposing the second resultant matrix, simultaneously computes one-dimensional partial fast Fourier transforms of each transposed-matrix block of subsequent rows of transposed-matrix blocks, one row of transposed-matrix blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each transposed-matrix block.

27. The data processing system of claim 25 , wherein the processing unit comprises a plurality of parallel-processing processing units.

28. The data processing system of claim 25 , wherein one of the parallel-processing processing units transposes the resultant matrix while a different parallel-processing processing unit computes the fast Fourier transform of one of the sections.

29. A computer-implemented data processing system for computing a multidimensional fast Fourier transform of an original matrix having rows and columns of data, the data processing system comprising:

a plurality of processing units; and

a memory having a program that:

divides the original matrix into a number of blocks of data, each block including at least one datum, the number of columns of data in each block being less than a total number of columns of data of the original matrix;

on a first processing unit of the plurality of processing units, locks a column of blocks and computes a one-dimensional partial fast Fourier transform of each block in the column of blocks, a result of the computations being stored in a resultant matrix having rows and columns;

on a second processing unit of the plurality of processing units, transposes 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, on at least a third processing unit of the plurality of processing units, simultaneously computes one-dimensional partial fast Fourier transforms of each block of subsequent columns of blocks, one column of blocks at a time, until one-dimensional partial fast Fourier transforms are computed for each block.

30. The data processing system of claim 29 , wherein the program divides the transposed matrix into a number of transposed-matrix blocks, each transposed-matrix block including at least datum, the number of columns in each transposed-matrix block being less than a total number of blocks of the transposed matrix;

computes a one-dimensional partial fast Fourier transform of each transposed-matrix block in a column of transposed-matrix blocks, a result of the computations being stored in a second resultant matrix having rows and columns;

transposes the second resultant matrix to a final matrix having rows and columns; and

while transposing the second resultant matrix, simultaneously computes one-dimensional partial fast Fourier transforms of each transposed-matrix block of subsequent columns of transposed-matrix blocks, one column of transposed-matrix sections at a time, until one-dimensional partial fast Fourier transforms are computed for each transposed-matrix section.

31. The data processing system of claim 29 , wherein the processing unit comprises a plurality of parallel-processing processing units.

32. The data processing system of claim 29 , wherein one of the parallel-processing processing units transposes the resultant matrix while a different parallel-processing processing unit computes the fast Fourier transform of one of the sections.

33. A computer-implemented data processing system for computing a multidimensional fast Fourier transform of an original matrix having rows and columns of data, the data processing system comprising:

means for 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;

means for a first processor of a plurality of processors locking a row of blocks and computing a one-dimensional partial fast Fourier transform of each block in a row of blocks, a result of the computations being stored in a resultant matrix having rows and columns;

means for 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

means for, while transposing the resultant matrix, at leas 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.