# 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