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

<p>@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.",
}</p>

<p>Here is the <a href="http://toms.acm.org/Upcoming.html" rel="nofollow">journal page</a>, and here is a <a href="http://www8.cs.umu.se/research/uminf/reports/2010/005/part1.pdf" rel="nofollow">pdf version</a> of the paper.
I hope this can be useful.</p>

CC BY-SA 3.0
2011-11-30T15:08:21.950Z
2011-11-30T15:15:01.307Z
2011-11-30T15:15:01.307Z
Massimo Cafaro
<p>You could look at <a href="http://onlinelibrary.wiley.com/doi/10.1111/j.1365-2966.2010.17587.x/abstract" rel="nofollow">this paper</a>, 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.</p>

CC BY-SA 3.0
2011-12-01T14:11:12.100Z
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
CC BY-SA 3.0
2011-12-01T13:55:55.323Z
2011-12-01T13:55:55.323Z
Peter Shor 
<p>Load two blocks that fit in cache then write them back out transposed? Depends on how they are stored if you want a parallelization.</p>

CC BY-SA 3.0
2011-11-30T20:58:14.107Z
2011-11-30T20:58:14.107Z
Chad Brewbaker
<p>what is the current state of the art in fast and parallel matrix in-place transposition?</p>

<p>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.</p>

<p>Thanks!</p>

<p>PS:
Of course, we do <em>not</em> 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.</p>

<p>Some information can be found in this wikipedia article, whose references I did not find to be very helpful though: <a href="http://en.wikipedia.org/wiki/In-place_matrix_transposition" rel="nofollow" title="http://en.wikipedia.org/wiki/In-place_matrix_transposition">Wikipedia Entry</a>.</p>

CC BY-SA 3.0
2011-11-25T13:22:52.607Z
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
CC BY-SA 3.0
2011-11-25T17:26:55.297Z
@RaduGRIGore: Not optimal, if you take into account the memory hierarchy. (Some keywords: external memory model; I/O model; cache-oblivious algorithms.)
Jukka Suomela
CC BY-SA 3.0
2011-11-26T13:12:08.730Z
@Radu: This only workds with square matrices, does it? Otherwise please tell me about that algorithm.
shuhalo
CC BY-SA 3.0
2011-11-26T15:23:42.330Z
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
CC BY-SA 3.0
2011-11-26T15:36:41.923Z
Why transpose? Just return $i,j$ th element when asked for $j,i$ th element! ;-)
Pratik Deoghare
<ds.algorithms><co.combinatorics><ds.data-structures><dc.parallel-comp>
parallelizable fast matrix in-place transposition
shuhalo
# parallelizable fast matrix in-place transposition

(Asked by: username_0 on 2011-11-25)

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](http://en.wikipedia.org/wiki/In-place_matrix_transposition "http://en.wikipedia.org/wiki/In-place_matrix_transposition").

**Tags:** ds.algorithms, co.combinatorics, ds.data-structures, dc.parallel-comp
> **Comments:**
> **username_1**: 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}$?  
> **username_2**: @RaduGRIGore: Not optimal, if you take into account the memory hierarchy. (Some keywords: external memory model; I/O model; cache-oblivious algorithms.)  
> **username_0**: @Radu: This only workds with square matrices, does it? Otherwise please tell me about that algorithm.  
> **username_3**: 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.  
> **username_4**: Why transpose? Just return $i,j$ th element when asked for $j,i$ th element! ;-)  

---

## 3 answers

### Answer by username_5 on 2011-11-30. Score: 4 | Accepted answer

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](http://toms.acm.org/Upcoming.html), and here is a [pdf version](http://www8.cs.umu.se/research/uminf/reports/2010/005/part1.pdf) of the paper.
I hope this can be useful.


---

### Answer by username_6 on 2011-12-01. Score: 3

You could look at [this paper](http://onlinelibrary.wiley.com/doi/10.1111/j.1365-2966.2010.17587.x/abstract), 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.

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_7 on 2011-11-30. Score: -2

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


---

