next up previous
Next: Fast Fourier Transforms Up: Contents Previous: Slow Fourier Transforms

Danielson-Lanczos Lemma

G. C. Danielson and C. Lanczos, ``Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids'', J. Franklin Inst. 233, 365 (1942).
For even $n = 2 m$:

X_k &=& \sum_{j=0, {\rm even}}^{n-1} \omega_n^{k j} x_j +
... +
\omega_n^k \sum_{j'=0}^{m-1} \omega_m^{k j'} x_{j'}^{\rm odd}

since $\omega_n^{2 k} = \omega_{n/2}^k$ and writing $x_k^{\rm even} =
x_{2 k}$ and $x_k^{\rm odd} = x_{2 k + 1}$.

Peter D. Haynes 2001-11-07