An efficient method for transposing large matrices and its application to separable processing of two-dimensional signals

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.