1

Exactly which FFT algorithm does Matlab use for the fft function? I though originally it was the Cooley-Tukey Decimation in Time algorithm but the Matlab documentation does not give a reference to exactly which algorithm is used. It does however reference to this page but there isn't any mathematical information that I can extract from that page which would help me understand the exact algorithm used by Matlab.

  • 2
    Look at this. It's definitely not just one algorithm, it's a bit more complicated ... – Matt L. Apr 27 '23 at 13:58
  • Cooley-Tukey is the basic idea of the FFT. Their paper is about 60 years old now. That means that there has been 60 years of research into improving it, and creating similar algorithms that work on non-power-of-two lengths. FFTW is quite old now too, but it contains fast algorithms for lengths that are multiples of 2, 3, 5, 7, 13, etc., and even for prime lengths. It also has many different implementations, and it will pick the best implementation for any one given length and computer either through a heuristic or by measuring how long it takes to run each implementation. – Cris Luengo Apr 28 '23 at 01:28
  • I'd add that for x64 Intel MKL is usually faster than FFTW (At least in some tests). – Royi Apr 28 '23 at 07:49

1 Answers1

2

MATLAB calls FFTW. At worst, there's some wrapper code just for interfacing with FFTW (e.g. fetching array metadata). If that's not of interest, the question then is "how does FFTW work".

FFTW is open sourced, and references source code and explanatory material.

You ask for "mathematical information", but odds are, there's little beyond the standard FFT stuff (power-of-2, prime handling), or simply FFT math that can be searched for outside of MATLAB/FFTW context. A ton of the speedup comes instead from computer sciency stuff like caching, device management, etc - that's what makes some FFTs faster than others, not smarter math in sense of operations used. (... I guess, correct me if wrong)

Given that it's closed source and I've not seen it myself, I can't speak with 100% confidence, but I can say that any missing bits likely aren't interesting or informative. If it's about fastest FFT, FFTW doesn't always win anyway. If one seeks extra assurance, it's possible to "write a MEX-file that calls FFTW, and show it's just as fast as MATLAB’s own fft function" (thanks @CrisLuengo).

OverLordGoldDragon
  • 8,912
  • 5
  • 23
  • 74
  • Thank you for your answer. Makes sense that different smaller algorithms are used as needed! –  Apr 27 '23 at 14:57
  • MATLAB just links to the standard FFTW library. I don’t know why tweaks would be needed. – Cris Luengo Apr 28 '23 at 01:18
  • @CrisLuengo Yeah I should've posed that less confidently. I was thinking of the odd and implicit ways in which MATLAB manages objects and code execution relative to Python and C++, also that it follows Fortran rather than C arrangement in memory. I figured maybe a few wrapper tweaks. I'll reword it, but do you know for sure there's "nothing"? And how do you know? – OverLordGoldDragon Apr 28 '23 at 12:41
  • Knowing the FFTW API, I know it can be directly applied to the data in a MATLAB array. There are no tweaks needed. Fortean vs C memory ordering is just related to how you translate matrix indices to memory location; arrays are still a contiguous memory block just like everywhere else. And how MATLAB manages objects and interprets code is unrelated to any of this, that is all in the interface between the user and the computations, calling FFTW is part of the computations. – Cris Luengo Apr 28 '23 at 14:11
  • One way to show there are no tweaks would be to write a MEX-file that calls FFTW, and show it works just as fast as MATLAB’s own fft function. – Cris Luengo Apr 28 '23 at 14:11
  • @CrisLuengo Right. So of concern to some is the desire to know every minute detail, such that unless it's exactly call_fftw(input, **fixed_arguments), we want to know it. What I wonder is whether it's like that and FFTW handles everything else internally. PyTorch views, for example, track stride and contiguity - which is metadata that's stored separate from the array itself, I'd think? E.g. inputting into simple CuPy without enforcing contiguity is trouble - but MATLAB could pass meta to FFTW. Also GPU and differentiable arrays. Anyway I think I can summarize this as irrelevant (edited). – OverLordGoldDragon Apr 28 '23 at 14:33
  • In docs they do reference FFTW but from my experience MATLAB fft does not perfectly match C++ results. It is close though. – jojeck Apr 29 '23 at 08:24
  • 1
    And thanks @CrisLuengo ! I wanted to be checked on this. I'd rather someone like you have answered, but at the time I thought the question would end with Matt's reference, also didn't want to miss out rigging it into HNQ. Also jojek said something. – OverLordGoldDragon Apr 29 '23 at 13:13
  • 1
    @jojek Do you mean the rounding errors are not the same? Those would depend on which algorithm is chosen to compute (which would depend also on configuration options), and on compilation options. I sometimes get slightly different results just by recompiling with a new version of GCC. – Cris Luengo Apr 29 '23 at 14:37