0

I'm doing a project that focuses on comparing time complexity of different implementations of Fourier Transform. I tried to write my DFT but when comparing the result with numpy.fft.fft, it produces the wrong result for some cases. What do I miss here?

Link to the equation, I can't insert image because of having too few posts.

    def matrix_ft(f):
    """
    
       input : complex array f
       output: discrete Fourier transform
    
    """
    
       N = len(f)
       n, k = np.mgrid[0:N, 0:N] 
       A = np.exp(-2j * np.pi/N * n * k)

    return np.dot(A, f)

Test case 1: Different result with numpy.fft.fft

t = np.linspace(0, 2*np.pi, 10, endpoint=False)
f = np.sin(t)

f_matrix = matrix_dft(f)
f_numpy  = np.fft.fft(f)

f_matrix
> array([ 2.22044605e-16+0.00000000e+00j,  1.11022302e-16-5.00000000e+00j,
        1.11022302e-16+0.00000000e+00j,  4.44089210e-16+0.00000000e+00j,
        1.11022302e-16-2.22044605e-16j,  0.00000000e+00+1.98955933e-16j,
        1.11022302e-16+6.66133815e-16j, -1.77635684e-15+1.22124533e-15j,
        1.11022302e-16+1.55431223e-15j, -7.99360578e-15+5.00000000e+00j])

f_numpy
> array([ 1.22464680e-16+0.00000000e+00j, -5.66553890e-16-5.00000000e+00j,
        1.22464680e-16-2.11176968e-16j,  3.11710912e-16+0.00000000e+00j,
        1.22464680e-16-1.30514544e-16j,  9.72791780e-17+2.22044605e-16j,
        1.22464680e-16+1.30514544e-16j,  1.28089482e-16+2.22044605e-16j,
        1.22464680e-16+2.11176968e-16j, -5.82849082e-16+5.00000000e+00j])

Test case 2: Same result with numpy.fft.fft

np.random.seed(100)
f = np.random.random(24)
f_matrix = matrix_dft(f)
f_numpy  = np.fft.fft(f)

f_matrix
> array([11.61772624+0.00000000e+00j,  0.51001244+8.17777267e-01j,
       -0.67361744+8.81554569e-01j,  1.34236557+2.52809638e-01j,
       -1.82906718+5.75819347e-01j, -0.67967733-1.47217968e+00j,
       -1.72661431+1.27326093e+00j,  0.6567099 +4.24015640e-01j,
        2.52248197-1.69792599e+00j,  0.39772128+1.10074631e+00j,
        0.12550973-5.33123940e-01j, -0.07867153-1.10333536e+00j,
        0.28968614+4.50841445e-15j, -0.07867153+1.10333536e+00j,
        0.12550973+5.33123940e-01j,  0.39772128-1.10074631e+00j,
        2.52248197+1.69792599e+00j,  0.6567099 -4.24015640e-01j,
       -1.72661431-1.27326093e+00j, -0.67967733+1.47217968e+00j,
       -1.82906718-5.75819347e-01j,  1.34236557-2.52809638e-01j,
       -0.67361744-8.81554569e-01j,  0.51001244-8.17777267e-01j])

> f_numpy
array([11.61772624+0.00000000e+00j,  0.51001244+8.17777267e-01j,
       -0.67361744+8.81554569e-01j,  1.34236557+2.52809638e-01j,
       -1.82906718+5.75819347e-01j, -0.67967733-1.47217968e+00j,
       -1.72661431+1.27326093e+00j,  0.6567099 +4.24015640e-01j,
        2.52248197-1.69792599e+00j,  0.39772128+1.10074631e+00j,
        0.12550973-5.33123940e-01j, -0.07867153-1.10333536e+00j,
        0.28968614-5.55111512e-17j, -0.07867153+1.10333536e+00j,
        0.12550973+5.33123940e-01j,  0.39772128-1.10074631e+00j,
        2.52248197+1.69792599e+00j,  0.6567099 -4.24015640e-01j,
       -1.72661431-1.27326093e+00j, -0.67967733+1.47217968e+00j,
       -1.82906718-5.75819347e-01j,  1.34236557-2.52809638e-01j,
       -0.67361744-8.81554569e-01j,  0.51001244-8.17777267e-01j])
vanngao09
  • 94
  • 4
  • 1
    Your results are roughly equivalent by visual inspection, and `np.allclose()` returns `True`. – ddejohn Nov 14 '21 at 00:10
  • @ddejohn Okay, I understand. I did take account of the precision error but not sure how to evaluate that. Thanks for the np.allclose(). – vanngao09 Nov 14 '21 at 00:23

0 Answers0