3

I'm not sure if this is the best place to ask, please advice if not.

I'm performing the following test, to check the output of real-FFTs, and I'm getting surprisingly high errors. So a real-FFT only computes the FFT for frequencies 0,1,...,n/2+1 since, due to Hermitian symmetry, the rest of the data is redundant. Thus I'm checking the error between the output of the real-FFT, and those data from the complex-FFT. For example, in Python/Numpy:

def error(n):
    x=numpy.random.normal(0,1,n)
    y1=numpy.fft.fft(x)[:n//2+1]
    y2=numpy.fft.rfft(x)
    err=numpy.max(abs(y1-y2))/numpy.max(abs(y1))
    return err

I get the following results for the largest 5 errors, chosen from n=2,...,3000.

2917 5.023e-11
2939 5.153e-11
2927 5.175e-11
2687 5.445e-11
2837 5.598e-11

and by only checking even n's

2866 8.974e-12
2606 9.189e-12
2858 1.112e-11
2918 1.165e-11
2878 1.167e-11

Errors on the order of -11 seem fairly high to me, I would expect -14 at most. I've checked this on fftw also, and get the same results. Is this error inherent to the real-FFT algorithm, or am I mistaken in my understanding?

I just noticed that all those odd numbers are primes, and and evens are twice a prime number, suggesting that this error is related to the prime-factorization of the data used by the FFT algorithm.

Thanks!

Edit: for powers of two, the results are:

2 0.000e+00
4 0.000e+00
8 9.970e-16
32 1.452e-15
128 1.806e-15
16 1.847e-15
256 2.656e-15
64 2.962e-15
2048 3.184e-15
512 3.261e-15
1024 4.612e-15
8192 4.706e-15
4096 5.028e-15
16384 6.710e-15
nick maxwell
  • 231

0 Answers0