3D FFT's and Convolutions using FFTW

Question

I am trying to perform a of convolution 2 3-dimensional vectors using the FFTW3 library in C.

My question relates to the order in which the frequency domain appears and if it will make a difference to the final result.

In the FFTW documentation it dictates that in 1D complex FFT's the negative frequencies are in the second half of the array. Does this follow through with a 3D complex FFT as the documentation doesn't say? If this is the case how would it be stored? i.e in 1D it would be something like:

|+|+|+|+|-|-|-|-|

so what would it be in 3D (sorry, terrible as visualising these things).

Finally when convolving 2 3D vectors using the convolution theorem do I need to do anything because of the FFTW layout, or can I just do the pointwise product and then IFFT back?

Answer 1

In 1D, you are likely to obtain, more precisely, $f_0, f_1, f_2,\ldots, f_{N/2}, f_{-N/2+1},\ldots, f_{-1}$. In other words, the $N/2+1$ ones correspond to positive frequencies. In higher dimensions, the same applies. In 3D, you ought to get a "top-left-front" sub-cube of positive frequencies.

To reduce periodic artifacts, you could 3D window the data before, and take care of the values of the imaginary parts after IFFTing back. If the input data is real, they should be small, and you can keep the real part only. If not, something gone wrong.