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.

Improve this question
$\endgroup$
5
  • 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, 2011 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, 2011 at 17:26
  • $\begingroup$ @Radu: This only workds with square matrices, does it? Otherwise please tell me about that algorithm. $\endgroup$
    – shuhalo
    Nov 26, 2011 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, 2011 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, 2011 at 15:36

3 Answers 3

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2011 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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