Danielson-Lanczos Lemma
The Discrete Fourier Transform of length 
(where is Even) can be rewritten as the sum of twoDiscrete Fourier Transforms, each of length 
. One is formed from the Even-numbered points;the other from the Odd-numbered points. Denote the 
th point of the Discrete Fourier Transform by 
. Then
 | |
 |
and 
. This procedure can be applied recursively to break up the evenand Odd points to their 
Even and Odd points. If is a Power of 2, this procedure breaks up the originaltransform into 
transforms of length 1. Each transform of an individual point has 
forsome . By reversing the patterns of evens and odds, then letting 
and 
, the value of in Binary isproduced. This is the basis for the Fast Fourier Transform.See also Discrete Fourier Transform, Fast Fourier Transform, Fourier Transform
References
Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in C: The Art of Scientific Computing. Cambridge, England: Cambridge University Press, pp. 407-411, 1989.
- Backtracking
- Backus-Gilbert Method
- Backward Difference
- Bader-Deuflhard Method
- Baguenaudier
- Bailey's Method
- Bailey's Theorem
- Baire Category Theorem
- Baire Space
- Bairstow's Method
- Baker's Dozen
- Baker's Map
- Balanced ANOVA
- Balanced Incomplete Block Design
- B*-Algebra
- Ball
- Ballantine
- Ballieu's Theorem
- Ballot Problem
- Ball Triangle Picking
- Banach Algebra
- Banach Fixed Point Theorem
- Banach-Hausdorff-Tarski Paradox
- Banach Measure
- Banach Space