Item

Abstract

A mixed-radix perfect shuffle algorithm is presented for transposing multidimensional matrices larger than the available high-speed memory. This problem occurs often during the analysis of large data sets such as used in electron microscopy, light microscopy, X-ray crystallography, multidimensional NMR spectroscopy, etc. In its twi-dimensional form, the mixed-radix perfect shuffle transposing algorithm is more general and/or faster than previous algorithms. It is simple to understand and to the reverse mixed-radix perfect shuffle algorithms may also be used to perform multidimensional Fourier transforms without actually transposing the data. With the three-dimensional version of the algorithm, Fourier transforms of up to, say, 512×512×512 sampling points can be performed on a standard 1991 workstation. With the new transposing algorithm, multidimensional Fourier transforms are typically limited by the available secondary data storage capacity rather than by the amount of available high-speed memory of the