Algorithms for in‐place matrix transposition. (13th November 2018)

• Record Type: Journal Article
• Authors: Gustavson, Fred G.; Walker, David W.
• Is Part Of: Concurrency and computation. Volume 31:Number 13(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-11-13
• Subjects: matrix -- parallelism -- performance -- permutations -- transpose; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5071
• Languages: English
• ISSNs: 1532-0626

Abstract

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.