You are a guest. Restricted access. Read more.
SCaVis manual

# Fast Fourier transforms

Snippet from Wikipedia: Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform (DFT) and its inverse. Fourier analysis converts time (or space) to frequency and vice versa; an FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, fast Fourier transforms are widely used for many applications in engineering, science, and mathematics.

# FFT implementations

There are several packages dealing with the fast fourier transform (FFT) problem. We will discuss the fastest one, which uses many threads and the multicore computer architecture. It is based on the PrallelColt as implemented by Piotr Wendykier.

We will use DComplexFactory2D factory to create a random DenseDComplexMatrix2D matrix and perform FFT.

Code example

``` 1: #compute 2D Discrete Fourier Transform (DFT) of a random complex matrix:
2:
3: from cern.colt.matrix.tdcomplex import DComplexFactory2D
4: from edu.emory.mathcs.utils  import ConcurrencyUtils
5: from edu.emory.mathcs.jtransforms.fft import *
6:
7: ConcurrencyUtils.setNumberOfThreads(2)      # use 2 cores
8: M = DComplexFactory2D.dense.random(100,100) # random matrix
9: print type(M)
10: M.fft2() #  compute 2D DFT in-place
11: # print M.toString()
```

# Discrete Cosine Transform (DCT)

This example is based on the real DenseDoubleMatrix2D matrix.

You have a limited access to this part. Unlock this text after becoming a full member.

You can also use 3D matrix methods, see DenseDoubleMatrix3D

# Discrete Fourier transform (DFT) Transform

This is 1D DFT transform of a complex matrix 1000×1000 using several processing cores:

You have a limited access to this part. Unlock this text after becoming a full member.