TABLE OF CONTENTS Both the Fourier analysis and wavelet analysis provide us a chance to transform a given problem (usually defined in a space of piecewise polynomials) to a new problem in a different functional space [482,481]. At a matrix level, however, both the fast Fourier transforms and the fast wavelet transforms are indispensable tools for certain applications. Here we give a short introduction.
The fast Fourier transform (FFT) represents a fast method of implementing the same discrete Fourier transform (DFT) [465,310]. The DFT comes about from an attempt of representing a general (and maybe nonperiodic) function f ( t), only available at n equally-spaced discrete points 
, by trigonometric functions just as continuous periodic functions are represented by Fourier series or nonperiodic ones by Fourier transforms [300].
One may either use the so-called semi-discrete Fourier transforms by embedding these points into an infinite and periodic sequence, or simply use the Fourier transforms for the sampled function: 
, where the usual Delta function ? indicates a local pulse. Then the Fourier transform for f s( t) is
where 
. Note that F s( ?) is periodic with period 2 ?/ L (or periodic in variable ?L with period 2 ?) with n coefficients so it is sufficient to consider n equally-spaced samples of F s( ?
