f can be reconstructed from its discrete Fourier transformation G(f) by
|
f = ?*. G(f)/N where * denotes complex conjugation
-
?* is an N by N matrix and G(f) is a vector of length N
|
Most applications require both calculating FFT's and reconstructing functions from their FFT's
-
However these are essentially the same algorithm as seen above and so we only need to illustrate one case
-
Issues with parallelism and optimal performance are identical
|
For solving the Poisson equation and various other applications, we use variations on the FFT
-
The sin transform – use imaginary part of G
-
The cos transform – use real part of G
|