# parallelizable fast matrix in-place transposition

what is the current state of the art in fast and parallel matrix in-place transposition?

I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, they do not include very detailed descriptions.

Thanks!

PS: Of course, we do not restrict to square matrices, but rather arbitrary rectangular matrices. Their memory layout is usually a linear sequence of entries in the memory (say, as in C) and it is a highly non-trivial task to convert this data block in-place/in-situ to the sequence that corresponds to the transposed matrix.

Some information can be found in this wikipedia article, whose references I did not find to be very helpful though: Wikipedia Entry.

• I probably miss something, but what's wrong with running ${n \choose 2}$ processes in parallel for each $0\le i<j<n$ to swap $A_{ij}$ with $A_{ji}$? – Radu GRIGore Nov 25 '11 at 13:22
• @RaduGRIGore: Not optimal, if you take into account the memory hierarchy. (Some keywords: external memory model; I/O model; cache-oblivious algorithms.) – Jukka Suomela Nov 25 '11 at 17:26
• @Radu: This only workds with square matrices, does it? Otherwise please tell me about that algorithm. – shuhalo Nov 26 '11 at 13:12
• I would break the problem into two subproblems: (1) What is the cycle decomposition of the permutation which corresponds to in-place matrix transposition? This part is discussed in Wikipedia. (2) How do we implement a cycle in parallel? This part sounds like it should be studied very well, although I am not an expert and I do not know any reference. – Tsuyoshi Ito Nov 26 '11 at 15:23
• Why transpose? Just return $i,j$ th element when asked for $j,i$ th element! ;-) – Pratik Deoghare Nov 26 '11 at 15:36

## 3 Answers

Sorry, no pseudocode, but a recent paper with a fast parallel algorithm, to appear in ACM Transactions on Mathematical Software:

@Article{Gustavson:2011:PCE, author = "Fred Gustavson and Lars Karlsson and Bo K{\aa}gstr{\"o}m", title = "Parallel and Cache-Efficient In-Place Matrix Storage Format Conversion", journal = "{ACM} Transactions on Mathematical Software", accepted = "8 July 2010", upcoming = "true", abstract = " Techniques and algorithms for efficient in-place conversion to and from standard and blocked matrix storage formats are described. Such functionality is required by numerical libraries that use different data layouts internally. Parallel algorithms and a software package for in-place matrix storage format conversion based on in-place matrix transposition are presented and evaluated. A new algorithm for in-place transposition which efficiently determines the structure of the transposition permutation a priori is one of the key ingredients. It enables effective load balancing in a parallel environment.", }

Here is the journal page, and here is a pdf version of the paper. I hope this can be useful.

You could look at this paper, which gives a proposal for how to solve this problem for a practical application in radio astronomy. One of the authors is quite knowledgeable about computer science, so they're not rediscovering the wheel here.

• Interesting paper, even though it deals with a slightly different version of the problem: transposing a matrix through an out of core, hardware implementation using FPGA etc. Thank you for sharing this. – Massimo Cafaro Dec 1 '11 at 14:11

Load two blocks that fit in cache then write them back out transposed? Depends on how they are stored if you want a parallelization.