Why is FFT of (A+B) different from FFT(A) + FFT(B)?

Question

I have been fighting with a very weird bug for almost a month. Asking you guys is my last hope. I wrote a program in C that integrates the 2d Cahn–Hilliard equation using the Implicit Euler (IE) scheme in Fourier (or reciprocal) space:

Where the "hats" mean that we are in Fourier space: h_q(t_n+1) and h_q(t_n) are the FTs of h(x,y) at times t_n and t_(n+1), N[h_q] is the nonlinear operator applied to h_q, in Fourier space, and L_q is the linear one, again in Fourier space. I don't want to go too much into the details of the numerical method I am using, since I am sure that the problem is not coming from there (I tried using other schemes).

My code is actually quite simple. Here is the beginning, where basically I declare variables, allocate memory and create the plans for the FFTW routines.

# include <stdlib.h> # include <stdio.h> # include <time.h> # include <math.h> # include <fftw3.h> # define pi M_PI  int main(){  // define lattice size and spacing int Nx = 150;         // n of points on x int Ny = 150;         // n of points on y double dx = 0.5;      // bin size on x and y  // define simulation time and time step long int Nt = 1000;   // n of time steps double dt = 0.5;      // time step size  // number of frames to plot (at denominator) long int nframes = Nt/100;  // define the noise double rn, drift = 0.05;   // punctual drift of h(x) srand(666);                // seed the RNG  // other variables int i, j, nt;    // variables for space and time loops  // declare FFTW3 routine fftw_plan FT_h_hft;   // routine to perform  fourier transform fftw_plan FT_Nonl_Nonlft; fftw_plan IFT_hft_h;  // routine to perform  inverse fourier transform  // declare and allocate memory for real variables double *Linft = fftw_alloc_real(Nx*Ny); double *Q2 = fftw_alloc_real(Nx*Ny); double *qx = fftw_alloc_real(Nx); double *qy = fftw_alloc_real(Ny);  // declare and allocate memory for complex  variables fftw_complex *dh = fftw_alloc_complex(Nx*Ny); fftw_complex *dhft = fftw_alloc_complex(Nx*Ny); fftw_complex *Nonl = fftw_alloc_complex(Nx*Ny); fftw_complex *Nonlft = fftw_alloc_complex(Nx*Ny);  // create the FFTW plans FT_h_hft = fftw_plan_dft_2d ( Nx, Ny, dh, dhft, FFTW_FORWARD, FFTW_ESTIMATE ); FT_Nonl_Nonlft = fftw_plan_dft_2d ( Nx, Ny, Nonl, Nonlft, FFTW_FORWARD, FFTW_ESTIMATE ); IFT_hft_h = fftw_plan_dft_2d ( Nx, Ny, dhft, dh, FFTW_BACKWARD, FFTW_ESTIMATE );  // open file to store the data char acstr[160]; FILE *fp; sprintf(acstr, "CH2d_IE_dt%.2f_dx%.3f_Nt%ld_Nx%d_Ny%d_#f%.ld.dat",dt,dx,Nt,Nx,Ny,Nt/nframes); 

After this preamble, I initialise my function h(x,y) with a uniform random noise, and I also take the FT of it. I set the imaginary part of h(x,y), which is dh[i*Ny+j][1] in the code, to 0, since it is a real function. Then I calculate the wavevectors qx and qy, and with them, I compute the linear operator of my equation in Fourier space, which is Linft in the code. I consider only the - fourth derivative of h as the linear term, so that the FT of the linear term is simply -q^4... but again, I don't want to go into the details of my integration method. The question is not about it.

// generate h(x,y) at initial time for ( i = 0; i < Nx; i++ ) {   for ( j = 0; j < Ny; j++ ) {     rn = (double) rand()/RAND_MAX;    // extract a random number between 0 and 1     dh[i*Ny+j][0] = drift-2.0*drift*rn;    // shift of +-drift     dh[i*Ny+j][1] = 0.0;   } }  // execute plan for the first time fftw_execute (FT_h_hft);  // calculate wavenumbers for (i = 0; i < Nx; i++) { qx[i] = 2.0*i*pi/(Nx*dx); } for (i = 0; i < Ny; i++) { qy[i] = 2.0*i*pi/(Ny*dx); } for (i = 1; i < Nx/2; i++) { qx[Nx-i] = -qx[i]; } for (i = 1; i < Ny/2; i++) { qy[Ny-i] = -qy[i]; }  // calculate the FT of the linear operator for ( i = 0; i < Nx; i++ ) {   for ( j = 0; j < Ny; j++ ) {     Q2[i*Ny+j] = qx[i]*qx[i] + qy[j]*qy[j];     Linft[i*Ny+j] = -Q2[i*Ny+j]*Q2[i*Ny+j];   } } 

Then, finally, it comes the time loop. Essentially, what I do is the following:

• Every once in a while, I save the data to a file and print some information on the terminal. In particular, I print the highest value of the FT of the Nonlinear term. I also check if h(x,y) is diverging to infinity (it shouldn't happen!),

• Calculate h^3 in direct space (that is simply dh[i*Ny+j][0]*dh[i*Ny+j][0]*dh[i*Ny+j][0]). Again, the imaginary part is set to 0,

• Take the FT of h^3,

• Obtain the complete Nonlinear term in reciprocal space (that is N[h_q] in the IE algorithm written above) by computing -q^2*(FT[h^3] - FT[h]). In the code, I am referring to the lines Nonlft[i*Ny+j][0] = -Q2[i*Ny+j]*(Nonlft[i*Ny+j][0] -dhft[i*Ny+j][0]) and the one below, for the imaginary part. I do this because:

• Advance in time using the IE method, transform back in direct space, and then normalise.

Here is the code:

for(nt = 0; nt < Nt; nt++) {  if((nt % nframes)== 0) {   printf("%.0f %%\n",((double)nt/(double)Nt)*100);   printf("Nonlft   %.15f \n",Nonlft[(Nx/2)*(Ny/2)][0]);    // write data to file   fp = fopen(acstr,"a");   for ( i = 0; i < Nx; i++ ) {     for ( j = 0; j < Ny; j++ ) {       fprintf(fp, "%4d  %4d  %.6f\n", i, j, dh[i*Ny+j][0]);       }   }   fclose(fp);  }  // check if h is going to infinity if (isnan(dh[1][0])!=0) {   printf("crashed!\n");   return 0; }  // calculate nonlinear term h^3 in direct space for ( i = 0; i < Nx; i++ ) {   for ( j = 0; j < Ny; j++ ) {       Nonl[i*Ny+j][0] = dh[i*Ny+j][0]*dh[i*Ny+j][0]*dh[i*Ny+j][0];       Nonl[i*Ny+j][1] = 0.0;   } }  // Fourier transform of nonlinear term fftw_execute (FT_Nonl_Nonlft);  // second derivative in Fourier space is just multiplication by -q^2 for ( i = 0; i < Nx; i++ ) {   for ( j = 0; j < Ny; j++ ) {     Nonlft[i*Ny+j][0] = -Q2[i*Ny+j]*(Nonlft[i*Ny+j][0] -dhft[i*Ny+j][0]);     Nonlft[i*Ny+j][1] = -Q2[i*Ny+j]*(Nonlft[i*Ny+j][1] -dhft[i*Ny+j][1]);   } }  // Implicit Euler scheme in Fourier space  for ( i = 0; i < Nx; i++ ) {     for ( j = 0; j < Ny; j++ ) {       dhft[i*Ny+j][0] = (dhft[i*Ny+j][0] + dt*Nonlft[i*Ny+j][0])/(1.0 - dt*Linft[i*Ny+j]);       dhft[i*Ny+j][1] = (dhft[i*Ny+j][1] + dt*Nonlft[i*Ny+j][1])/(1.0 - dt*Linft[i*Ny+j]);     } }  // transform h back in direct space fftw_execute (IFT_hft_h);  // normalize for ( i = 0; i < Nx; i++ ) {   for ( j = 0; j < Ny; j++ ) {       dh[i*Ny+j][0] = dh[i*Ny+j][0] / (double) (Nx*Ny);       dh[i*Ny+j][1] = dh[i*Ny+j][1] / (double) (Nx*Ny);   } }  } 

Last part of the code: empty the memory and destroy FFTW plans.

// terminate the FFTW3 plan and free memory fftw_destroy_plan (FT_h_hft); fftw_destroy_plan (FT_Nonl_Nonlft); fftw_destroy_plan (IFT_hft_h);  fftw_cleanup();  fftw_free(dh); fftw_free(Nonl); fftw_free(qx); fftw_free(qy); fftw_free(Q2); fftw_free(Linft); fftw_free(dhft); fftw_free(Nonlft);  return 0;  } 

If I run this code, I obtain the following output:

0 % Nonlft   0.0000000000000000000 1 % Nonlft   -0.0000000000001353512 2 % Nonlft   -0.0000000000000115539 3 % Nonlft   0.0000000001376379599  ...  69 % Nonlft   -12.1987455309071730625 70 % Nonlft   -70.1631962517720353389 71 % Nonlft   -252.4941743351609204637 72 % Nonlft   347.5067875825179726235 73 % Nonlft   109.3351142318568633982 74 % Nonlft   39933.1054502610786585137 crashed! 

The code crashes before reaching the end and we can see that the Nonlinear term is diverging.

Now, the thing that doesn't make sense to me is that if I change the lines in which I calculate the FT of the Nonlinear term in the following way:

// calculate nonlinear term h^3 -h in direct space for ( i = 0; i < Nx; i++ ) {   for ( j = 0; j < Ny; j++ ) {       Nonl[i*Ny+j][0] = dh[i*Ny+j][0]*dh[i*Ny+j][0]*dh[i*Ny+j][0] -dh[i*Ny+j][0];       Nonl[i*Ny+j][1] = 0.0;   } }  // Fourier transform of nonlinear term fftw_execute (FT_Nonl_Nonlft);  // second derivative in Fourier space is just multiplication by -q^2 for ( i = 0; i < Nx; i++ ) {   for ( j = 0; j < Ny; j++ ) {     Nonlft[i*Ny+j][0] = -Q2[i*Ny+j]* Nonlft[i*Ny+j][0];      Nonlft[i*Ny+j][1] = -Q2[i*Ny+j]* Nonlft[i*Ny+j][1];   } } 

Which means that I am using this definition:

instead of this one:

Then the code is perfectly stable and no divergence happens! Even for billions of time steps! Why does this happen, since the two ways of calculating Nonlft should be equivalent?

Thank you very much to anyone who will take the time to read all of this and give me some help!

EDIT: To make things even more weird, I should point out that this bug does NOT happen for the same system in 1D. In 1D both methods of calculating Nonlft are stable.

EDIT: I add a short animation of what happens to the function h(x,y) just before crashing. Also: I quickly re-wrote the code in MATLAB, which uses Fast Fourier Transform functions based on the FFTW library, and the bug is NOT happening... the mystery deepens.

Answer 1

I solved it!! The problem was the calculation of the Nonl term:

  Nonl[i*Ny+j][0] = dh[i*Ny+j][0]*dh[i*Ny+j][0]*dh[i*Ny+j][0];   Nonl[i*Ny+j][1] = 0.0; 

That needs to be changed to:

  Nonl[i*Ny+j][0] = dh[i*Ny+j][0]*dh[i*Ny+j][0]*dh[i*Ny+j][0] -3.0*dh[i*Ny+j][0]*dh[i*Ny+j][1]*dh[i*Ny+j][1];   Nonl[i*Ny+j][1] = -dh[i*Ny+j][1]*dh[i*Ny+j][1]*dh[i*Ny+j][1] +3.0*dh[i*Ny+j][0]*dh[i*Ny+j][0]*dh[i*Ny+j][1]; 

In other words: I need to consider dh as a complex function (even though it should be real).

Basically, because of stupid rounding errors, the IFT of the FT of a real function (in my case dh), is NOT purely real, but will have a very small imaginary part. By setting Nonl[i*Ny+j][1] = 0.0 I was completely ignoring this imaginary part. The issue, then, was that I was recursively summing FT(dh), dhft, and an object obtained using the IFT(FT(dh)), this is Nonlft, but ignoring the residual imaginary parts!

Nonlft[i*Ny+j][0] = -Q2[i*Ny+j]*(Nonlft[i*Ny+j][0] -dhft[i*Ny+j][0]); Nonlft[i*Ny+j][1] = -Q2[i*Ny+j]*(Nonlft[i*Ny+j][1] -dhft[i*Ny+j][1]); 

Obviously, calculating Nonlft as dh^3 -dh and then doing

Nonlft[i*Ny+j][0] = -Q2[i*Ny+j]* Nonlft[i*Ny+j][0];  Nonlft[i*Ny+j][1] = -Q2[i*Ny+j]* Nonlft[i*Ny+j][1]; 

Avoided the problem of doing this "mixed" sum.

Phew... such a relief! I wish I could assign the bounty to myself! :P

EDIT: I'd like to add that, before using the fftw_plan_dft_2d functions, I was using fftw_plan_dft_r2c_2d and fftw_plan_dft_c2r_2d (real-to-complex and complex-to-real), and I was seeing the same bug. However, I suppose that I couldn't have solved it if I didn't switch to fftw_plan_dft_2d, since the c2r function automatically "chops off" the residual imaginary part coming from the IFT. If this is the case and I'm not missing something, I think that this should be written somewhere on the FFTW website, to prevent users from running into problems like this. Something like "r2c and c2r transforms are not good to implement pseudospectral methods".

EDIT: I found another SO question that addresses exactly the same problem.