Fast Fourier Transform in Arbitrary Precision

by Pavel Holoborodko on April 11, 2012

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:

Y = fft(x)
Y = fft(X,n)
Y = fft(X,[],dim)
Y = fft(X,n,dim)
y = ifft(X)
y = ifft(X,n)
y = ifft(X,[],dim)
y = ifft(X,n,dim)
y = ifft(..., 'symmetric')
y = ifft(..., 'nonsymmetric')


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.

{ 0 comments… add one now }

Leave a Comment

Previous post:

Next post: