6.4 Fast Fourier Transformation

Fourier transformation bases on the decomposition into a sequence of certain frequencies (eigenfrequencies) expressed by the trigonometric functions $\sin$ and $\cos$. If the number of eigenfrequencies is $N=2^P-1$ then this decomposition can be accelerated significantly and is called Fast Fourier Transformation (FFT).

Approach :

• Signal processing,
• Partial differential equations in rectangular domains,
• Preconditioning of cyclic matrices (BEM).

Ex.: Partial differential equation in the unit square

We have to determine the unknown function $u$ from the pde in $\Omega = (0,1)^2$.

$$\boxed{\begin{array}{rcll} - \triangle u + c u &=& f & \mbox{... ... \\ u &=& \varphi (:= 0) & \mbox{on} \;\Gamma = \partial\Omega \end{array}}$$

The domain is discretized by an equidistant grid ($N+1$ grid lines in each dimension) and the differential operator will be approximated by a 5-point difference stencil.

$\Longrightarrow$ $(4+ch^2) u_{i,j} - (u_{i,j-1} + u_{i,j+1} + u_{i-1,j} + u_{i+1,j}) = h^2 f_{i,j}$ $i,j = \overline{1,N-1} \makebox[0pt]{}$


$\Longrightarrow$ $\Lambda \underline{u} = \underline{f}$

The discretized differential operator $\Lambda$ from the example above possesses the eigenfrequencies

$$\mu_{k,\ell}(ih,jh) \;=\; 2 \sin(k\pi i h) \sin(\ell\pi j h) \qquad{\scriptstyle k,\ell = \overline{1,N-1} \makebox[0pt]{}}$$

and appropriate eigenvalues

$$\lambda_{k,\ell} \;=\; 4 \left[ \sin^2\tfrac{k \pi h}{2} + \sin^2\tfrac{\ell \pi h}{2} \right] + c h^2 \enspace.$$

The right hand side $f$ and the unknown function $u$ can be expressed as linear combination of the eigenfrequencies.

$$\begin{eqnarray}f_{i,j} = f(ih,jh) &=& \sum\limits_{k,\ell = 1}^{... ...limits_{k,\ell = 1}^{N-1} \beta_{k,\ell}\cdot\mu_{k,\ell}(ih,jh) \end{eqnarray}$$ (6.7a)

Now, we can achieve the result of the pde as follows :

1. Express $f$ in terms of eigenfrequencies  $\mu_{k,\ell}$ (Fourier analysis)
   $\Longrightarrow$ Determine the coefficients  $\gamma_{k,\ell}$ in (6.7a).
2. Divide the coefficients with the eigenvalues of the discretized differential operator ($\approx$ inversion of operator)
   $\Longrightarrow$ $\beta_{k,\ell} := \frac{\gamma_{k,\ell}}{\lambda_{k,\ell}}$
3. Calculate the discrete approximate solution (Fourier synthesis)
   $\Longrightarrow$ $u(ih,jh)$ in (6.7b)

Items 1 and 3 are realized via (fast) Fourier transformation.