Optimizing Fourier transforms

From Octave
Revision as of 23:06, 13 June 2019 by Siko1056 (talk | contribs) (Improve markup.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Octave uses the package FFTW version 3 to perform its fast fourier transforms, which is a highly optimized fast fourier transform package. This package uses what it calls "wisdom" to plan the best way to perform the fast fourier transform on your particular computer. Such "wisdom" being dependent on the machine on which FFTW is used can not easily be shared, though in practice using wisdom from architecturally similar machines seems ok.

Due to particularities of how wisdom is created, Octave can't create this wisdom directly from the fast fourier transform commands themselves, and in the absence of any "wisdom" an estimate is used that in most cases is not too bad. However, Octave includes the command fftw_wisdom to create and manage such "wisdom". For example

 fftw_wisdom ([102, 0, 0; 103, 103, 0; 102, 103, 105]);
 a = fft (rand (1,102));
 b = fft (rand (103,103));
 c = fftn (rand ([102, 103, 105]));

calculates the wisdom necessary to accelerate the 102, 103x103 and the 102x103x105 FFTs. Note that calculated wisdom will be lost when restarting Octave. As the calculation of the wisdom is effectively performed by doing the fast fourier transform in many different ways to find the fastest version, this means that the above is only useful if you intend to do many many fourier transforms of this form.

Octave also has the ability to use "wisdom" that is stored in a file, and the fftw_wisdom command can equally be used to manage such wisdom. By far the best way to handle FFTW wisdom files is to create a system-wide wisdom file. This file is managed by FFTW itself, and so all applications linked to FFTW will benefit from this "wisdom" file. For this purpose FFTW itself it delivered with a program fftw-wisdom that can be used like

 % fftw-wisdom -v -c -o /etc/fftw/wisdom

to create a system-wide "wisdom" file in /etc/fftw/wisdom. The -c option specifies than canonical wisdom is created, which implies that wisdom for the fourier transforms in one-, two- or three-dimension with dimensions that are integer powers of 2 or 10 with fewer than 2^20 elements are calculated. That "wisdom" for the transform 16x16 or 100x1 will be calculated but the "wisdom" for transforms like 16x17 or 101x1 will not be. However, "wisdom" for arbitrary transforms can be created with the fftw-wisdom command.

You are recommended to read the help file of the Octave command fftw_wisdom (note that this is fftw-underscore-wisdom) and FFTW's command fftw-wisdom (fftw-dash-wisdom) for further information.