We have developed an efficient algorithm for transposing large matrices in place. The algorithm is efficient because data are accessed either sequentially in blocks or randomly within blocks small enough to fit in cache, and because the same indexing calculations are shared among identical procedures operating on independent subsets of the data. This inherent parallelism makes the method well suited for a multiprocessor computing environment. The algorithm is easy to implement because the same two procedures are applied to the data in various groupings to carry out the complete transpose operation. Using only a single processor, we have demonstrated nearly an order of magnitude increase in speed over the previously published algorithm by Gate and Twigg for transposing a large rectangular matrix in place. With multiple processors operating in parallel, the processing speed increases almost linearly with the number of processors. A simplified version of the algorithm for square matrices is presented as well as an extension for matrices large enough to require virtual memory.

An attempt is made to transpose an arbitrary matrix when the total number of matrix elements is too large to store them all in random-access memory. This problem is often a computational bottleneck in large computed-imaging problems. A simple algorithm for obtaining the transposed matrix using only two read/write passes over the data is derived. This algorithm is efficient for a wide range of practical problems. The first step of the algorithm reorders the data in a form that permits efficient access to the data either by row or by column. Thus, if the only reason for constructing the transpose is to provide efficient access to the data for processing along the slow dimension of a two-dimensional data set, the matrix transpose can be eliminated simply by storing the data in this intermediate form. Furthermore, this reordering can be performed in place with a single read/write pass over the data.

The short-time Fourier transform (STFT) formally represents the output of a filter-bank spectrum analyzer as a two-dimensional function of time and frequency. For the case of a Gaussian analysis window, the log magnitude and phase of the STFT are related by a coupled pair of first order linear partial differential equations. Moreover, the log magnitude and phase independently satisfy second order linear partial differential equations. Because not all functions of time and frequency are STFT's, the second order equations provide a test for determining whether a particular magnitude or phase function corresponds to the magnitude or phase of a STFT obtained with a Gaussian analysis window. Furthermore, given a valid magnitude (or phase) function, the pair of first order equations can be integrated to determine the corresponding phase (or magnitude) function.