In a numerical computation, I am required to take a multi-dimensional FFT on a distributed-memory cluster. The data is currently distributed using a distributed array in PETSc (DMDA).

I initial looked at the distributed version of FFTW. However, the layout of my data does not conform to the layout used by FFTW. Therefore, I would need to scatter my data to the layout required by FFTW which would not be ideal. See link for an example using PETSc.

Note, the FFT is not the dominant bottleneck in my computation. I just want to minimize the communication overhead required for the FFT. Does anyone have any suggestions for what I should be using? Is FFTW the optimal approach even when my data does not conform to FFTW layout?

  • $\begingroup$ I could construct a multi-dimensional transform using multiple 1d FFTW transforms. I don't know if this is the most efficient way of doing this though. $\endgroup$
    – Eldila
    Commented Feb 11, 2013 at 6:36
  • $\begingroup$ I came across an FFT developed at the Sandia National Laboratories which might have some potential. sandia.gov/~sjplimp/docs/fft/README.html $\endgroup$
    – Eldila
    Commented Feb 11, 2013 at 6:44

1 Answer 1


Michael Pippig at the University of Chemnitz (Germany) has implemented an MPI-parallelized FFT that uses FFTW in the background. This might help you: http://www-user.tu-chemnitz.de/~mpip/software.php?lang=en

It is using the algorithm proposed by Plimpton from Sandia National Labs as suggested by Eldila's comment.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.