Patent Document ID: 9098449
Application ID: 13837055
Patent Status: 1

Claim One:
1. A method for computationally performing a Fast Fourier Transform (“FFT”) on n points, the method comprising: dividing the n points into a plurality of groups of m points, where m<n; performing a plurality of constant-geometry FFTs on each of the groups of m points, each constant-geometry FFT comprising: i. reading the m points from a computer memory into an input buffer; ii. computationally applying a butterfly operation to each of the m points; iii. writing results of the butterfly operation into an output buffer; and iv. storing transposed contents of the output buffer to the original location of the m points in the computer memory, thereby overwriting the original m points; and performing at least one in-place FFT on the results of the plurality of constant-geometry FFTs stored in the computer memory, thereby completing the FFT of the n points.