UPDATE (December 25, 2017): Fast Fourier Transform (FFT) routines have been updated with various speed optimizations, including multi-core parallelism, extended set of small FFT with minimum number of arithmetic operations, etc. Now toolbox uses split-radix for power-of-two, mixed-radix Stockham framework for composite and Bluestein algorithm for prime lengths FFT. All algorithms have been optimized for parallel execution and quadruple/multi-precision modes.

We do not use Kiss FFT library anymore, since it doesn’t allow parallel optimizations. Instead we have developed our own C++ library, focused on computations with arbitrary precision and speed.

We released our newest update a few days ago, and in it we have further upgraded the Multiprecision Computing Toolbox to now include Fast Fourier Transform functions capable of computing in arbitrary precision. The newly introduced FFT functions are optimized by performance, and are fully compatible with all of MATLAB’s equivalent routines.

All special cases of the functions are supported:

Both the direct and inverse transforms are optimized by speed, taking into account particular cases of real and conjugate complex sequences. Additionally, we employ specific optimization techniques when the input array length is of power of 2, or a composite number with simple factors 2,3,4, and 5.

Below is an example of a direct and inverse FFT of random data, accurate up to 100 decimal places:

>> mp.Digits(100);
>> x = mp.rand(100,100);
>> norm(x-ifft(fft(x)),1)
3.1e-103
 
>> tic; ifft(fft(x)); toc;
Elapsed time is 0.839798 seconds.

The Toolbox update is built upon the excellent Fast Fourier Transform library Kiss FFT, created by Mark Borgerding.