# Difference between revisions of "Fourier transform, discrete"

If a function is given on the set of points $t _ {k} = k \Delta t$ by its values $x _ {k}$, $k = 0 \dots N - 1$, $\Delta t = T/N$, where $T > 0$ is the period of the function, then the discrete Fourier transform of the vector $x = ( x _ {0} \dots x _ {N - 1 } )$ is the vector $\widehat{x} = Fx$, where $F$ is the matrix with entries
$$\mathop{\rm exp} \{ - 2 \pi i \omega _ {m} t _ {k} \} ,$$
$i$ is the imaginary unit, $\omega _ {m} = m \Delta \omega$, $m = 0 \dots N - 1$, $\Delta \omega = 1/T$. The components of the vector $\widehat{x}$ are analogues of the Fourier coefficients in the usual trigonometric expansions. The discrete Fourier transform is used to calculate approximately these coefficients, spectra, auto- and mutual-correlation functions, etc. A direct computation of the discrete Fourier transform requires about $N ^ {2}$ arithmetic operations and a great expenditure of machine time. The method of the fast Fourier transform (see ) enables one to reduce the number of operations considerably. When $N = n _ {1} \dots n _ {m}$, this method carries out the discrete Fourier transform approximately in $N ( n _ {1} + \dots + n _ {m} )$ operations, increasing the accuracy of the calculation. When $N = 2 ^ {m}$ there are algorithms which are particularly convenient in practice. There is a considerable number of programs realizing or using the fast Fourier transform to solve applied problems. The method of the fast Fourier transform includes widely known efficient methods for computing the discrete Fourier transform, for example, the Runge method (see  and Runge–Kutta method).