I'm trying to do FFT convolution via the FFTW3 library for image processing purposes. Basically I have a kernel and I am convolving it with an image. A problem I encountered has to do with the dimensions of the image. When the width is not equal to the height, the pixel values I get, seem to be at the wrong x,y coords. With the width and height being equal I get the correct results. My questions are: Is it possible to perform 2D FFT convolution with width not equal to height, without having to pad the image? Could it have to do with the way I'm padding the kernel to match the image size? I'm using an NVIDIA paper, available http://developer.download.nvidia.com/compute/cuda/2_2/sdk/website/projects/convolutionFFT2D/doc/convolutionFFT2D.pdf" [Broken] on the subject as a guide.