3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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}$? $\endgroup$ – Radu GRIGore Nov 25 '11 at 13:22
  • 2
    $\begingroup$ @RaduGRIGore: Not optimal, if you take into account the memory hierarchy. (Some keywords: external memory model; I/O model; cache-oblivious algorithms.) $\endgroup$ – Jukka Suomela Nov 25 '11 at 17:26
  • $\begingroup$ @Radu: This only workds with square matrices, does it? Otherwise please tell me about that algorithm. $\endgroup$ – shuhalo Nov 26 '11 at 13:12
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 26 '11 at 15:23
  • 1
    $\begingroup$ Why transpose? Just return $i,j$ th element when asked for $j,i$ th element! ;-) $\endgroup$ – Pratik Deoghare Nov 26 '11 at 15:36
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Massimo Cafaro Dec 1 '11 at 14:11
-2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.