FFT in stan-math/autocorr


Do FFT method in autocorr use the real number optimization (only first half is calculated)?

In python numpy this is used with rfft

See http://eigen.tuxfamily.org/index.php?title=EigenFFT

Real FFT half-spectrum

1. Other libraries: use only half the frequency spectrum (plus one extra sample for the Nyquist bin) for a real FFT, the other half is the conjugate-symmetric of the first half. This saves a copy and some memory. The downside is the caller needs to have special logic for the number of bins in complex vs real.
2. How Eigen::FFT differs: The full spectrum is returned from the forward transform. This facilitates generic template programming by obviating separate specializations for real vs complex. On the inverse transform, only half the spectrum is actually used if the expected output type is real.
3. Use the Eigen::FFT::HalfSpectrum flag to change the default behavior

It’s my understanding that we do not currently use the Eigen::FFT::HalfSpectrum flag. Later in the file autocorrelation.hpp only the first N real values are kept, so I can’t say I see why we don’t.

If this could be sped up, that’d be great. Matt Hoffman figured most of this out and I tried to code it the first time without really understanding it well. Most of the effort was involved in getting the padding right (no idea why these things don’t autopad—is it the memory?).

What we’d really like to do is get a version of FFT that we could include in the math lib.

1 Like