How is FFT implemented in RSF? What FFT conventions are used? What choices of array size are efficient?
There are two main fft programs: sffft1 and sffft3.
sffft1 takes real input and transforms it to complex by applying real-to-complex FFT on the first axis. It does the inverse transform when inv=y.
sffft3 applies complex-to-complex FFT on the specified axis. The sign of the transform is determined by the sign parameter.
sfcosft applies real-to-real cosine transform.
Here is an example 2-D FFT figure from Jon Claerbout reproduced in bei/ft1/plane4:
RSF utilizes the KISS FFT library for applying FFT. There are some faster open-source software solutions available, most notably FFTW but KISS (Keep It Simple, Stupid) FFT is attractive because of it simplicity and compactness. The library can handle an arbitrary data size. However, some sizes (prime factor powers) are more efficient than others. For example, here are CPU times for running sffft1 on files with different sizes:
| n1 | CPU time |
|---|---|
| 999,999 | 0.01 s |
| 1,000,000 | 0.01 s |
| 1,000,001 | 1.64 s |
Update: sffft1, sffft3, and some other programs that use FFT, now pad the data to the nearest optimal size.
> I see that *sffft3* can run on any axis. Is it more efficient to first
> transpose the desired axis into axis 1 or is it better to run *sffft3*
> directly on the desired axis?
It should be faster to run *sffft3* on the required axis unless you cannot fit the full data volume in memory, then *sftransp | sffft3 | sftransp* should work.
As soon as sourceforge starts working again, I will upload kissfft version 1.2.5 which has a function to help in this decision.
int kiss_fft_next_fast_size(int n)
{
while(1) {
int m=n;
while ( (m%2) == 0 ) m/=2;
while ( (m%3) == 0 ) m/=3;
while ( (m%5) == 0 ) m/=5;
if (m<=1) break; /* n is completely factorable by twos, threes, and fives */ n++; } return n; }
Update on FFT sizes:
sffft1, sffft3, sfcosft, and some other programs that use FFT, now pad the data to the nearest optimal size. The table of optimal sizes extends to about 10,000.
Mark, thank you! Your kiss_fft_next_fast_size is much more elegant. We have updated our programs.
Update on FFT sizes:
sffft1, sffft3, sfcosft, and some other programs that use FFT, now pad the data to the nearest optimal size.