SYLLABUS Previous: 4 FOURIER TRANSFORM
Up: 4 FOURIER TRANSFORM
Next: 4.2 Linear equations.
4.1 FFT with the computer
Slide : [
Complex 
CosineSine 
Numbering 
VIDEO
login]
In the same manner as for the linear solvers, it is sufficient to have a
rough idea of the underlying process to efficiently use the FFT routines
from software libraries. In fact, you should always privilege vendors
implementations, since these have in general been optimized for the
specific computer that you are using.
Having no library available in JAVA, a couple of routines from
Numerical Recipes
[24] have here been translated for JBONE and put into the
FFT.java
class  making as
little modification as possible to the original code so as to let you
learn more from the book.
The Complex.java
class has been included to illustrate how rewarding it is to work
with Netlib
[5] software.
Remember that a complex function
of period
can be
represented with a complex series

(1) 
On the other hand, you can use the cosinesine form

(2) 

(3) 
with the following relations that hold between the Fourier coefficients

(4) 
and only if
is real

(5) 
This is almost how the transformation has been implemented in
FFT.java, except that
 The number of modes is assumed to be an integer power of 2;
the creation of an FFTobject from data sampled on a mesh therefore
relies on the command
double f = new double[64];
FFT myFTObject = new FFT(f, FFT.inXSpace);
where FFT.inXSpace sets the original location of the variable
myFTObject in configuration space.
 To avoid negative indices for periodic functions
,
negative harmonics
are stored in wraparound order after
the positive components and are indexed by
. For a real function
sampled on a mesh
with a period
, the call to
Complex spectrum = new Complex[64];
double periodicity=64.;
spectrum = myFTObject.getFromKSpace(FFT.firstPart,periodicity);
for (int m=0; m<N; m++)
System.out.println("spectrum["+m+"] = "+spectrum[m]);
will print the nonzero components
spectrum[0] = (7. +0.0i)
spectrum[1] = (4. +0.0i) spectrum[63] = (4. +0.0i)
spectrum[2] = (0. +2.0i) spectrum[62] = (0. 2.0i)
spectrum[32]= (3. +0.0i)
It is easy to see that the shortest wavelength component [32] will
always be real if
is real, since
is sampled
exactly for multiples of
.
 Relying on the linearity of the FFT, two real numbers are
packed into one complex number and transformed for the cost of a single
complex transformation by initializing
double f = new double[64];
double g = new double[64];
FFT myPair = new FFT(f,g, FFT.inXSpace);
This is the reason for the argument FFT.firstPart used here above,
asking for the spectrum of only the first (and in this example the only)
function.
Apart from the array index which starts with [0] in JAVA,
the implementation is equivalent to the routines in
Numerical Recipes
[24] and indeed very similar to that of many computer vendors.
SYLLABUS Previous: 4 FOURIER TRANSFORM
Up: 4 FOURIER TRANSFORM
Next: 4.2 Linear equations.
