Algorithms for in‐place matrix transposition
Fred G. Gustavson, DAVID W. WALKER · Concurrency and Computation Practice and Experience · 2018
Summary This paper presents implementations of in‐place algorithms for transposing rectangular matrices. One implementation is a swap‐based algorithm described by Tretyakov and Tyrtyshnikov,1 to which we have introduced a number of variations. In particular, we show how the original algorithm can be modified to require constant additional memory. A proof of correctness is also sketched. This algorithm is compared with cycle‐following approaches and with the swap‐based GCD Transpose algorithm that partitions the matrix into a hierarchy of square submatrices. The performance of parallel implementations on a multicore system is also investigated.