


The number of complex multiplications for a Ddimensional transform is significantly
less than required by interative application of 1dimensional FFTs, the conventional
method for forming multidimensional FFTs.
The relative number of multiplications goes approximately as 2/D, for D > 2.
See note below.




Fewer multiplications mean greater speed of execution and less roundoff error
compared with iterative application of conventional 1dimensional FFTs.




The transform can be taken along any subset of the dimensions of the multidimensional
array. Moreover, the transforms along the selected dimensions are formed
simultaneously and do not require transposition or reordering of
the multidimensional array, which affords another significant time savings.
See note below.




Transforms in any direction through the array are always developed by operating along
the direction that the data are written. Therefore, transposition of data is
never required for arrays too large to fit into active memory,
completely eliminating the additional, and sometimes prohibitive, I/O overhead
associated with large external arrays. See note below.




Transforms of real data, as well as complex data, are computed in place, regardless
of the dimensionality of the transform, or the subset of directions along which the
transform is taken. That is, real transform results always fit
exactly within the space of the original real array, with no extra
storage required.




A complete package of routines is included for converting between normally ordered,
bitreversed, and packed (real transform) data.
