  The fast Fourier transform (FFT) is undoubtedly an essential primitive that
has been applied in various fields of science and engineering. In this paper,
we present a decomposition method for parallelization of multi-dimensional FFTs
with smallest communication amount for all ranges of the number of processes
compared to previously proposed methods. This is achieved by two distinguishing
features: adaptive decomposition and transpose order awareness. In the proposed
method, the FFT data are decomposed based on a row-wise basis that maps the
multi-dimensional data into one-dimensional data, and translates the
corresponding coordinates from multi-dimensions into one-dimension so that the
resultant one-dimensional data can be divided and allocated equally to the
processes. As a result, differently from previous works that have the
dimensions of decomposition pre-defined, our method can adaptively decompose
the FFT data on the lowest possible dimensions depending on the number of
processes. In addition, this row-wise decomposition provides plenty of
alternatives in data transpose, and different transpose order results in
different amount of communication. We identify the best transpose orders with
smallest communication amounts for the 3-D, 4-D, and 5-D FFTs by analyzing all
possible cases. Given both communication efficiency and scalability, our method
is promising in development of highly efficient parallel packages for the FFT.
