4

How is it possible to transpose a MxN matrix without using a "buffering" matrix? In the latter case it's easy and quite the "classic" approach...

Given a matrix[M][N], I would like to put it into a void transpose_matrix(int matrix[][]) function which operates directly on the matrix passed as reference which, as previosly said, would edit the matrix memory space to transpose its elements.

e.g:

A =

1 2 3 4
5 6 7 8
9 1 2 3

A after transposing itself (without pretty printing)[1]:

1 5 9 2
6 1 3 7
2 4 8 3

How would A looked like in a NxM matrix:

1 5 9
2 6 1
3 7 2
4 8 3

Thanks!

[1]: Printing the matrix as if it was actually a "new" NxM matrix.

  • 1
    Without seeing how the matrix will look in NxM form, I can only guess what you mean. Do you mean you have your MxN matrix in a linear array, interpreted as a matrix, and since your NxM matrix will physically fit into the same linear storage, you want to apply a transposing in-place in this linear array? – Doc Brown Jan 31 '15 at 9:12
  • By how is it possible, are you asking how to do it? (In which case, the answer is don't -- link to LAPACK etc) Or are you asking how it is done in some particular framework/hardware (such as how it is done in LAPACK, or How is it done in AMD64 cpus). Or perhaps how could it be done in hardware (It would be easy to build hardware that could transpose any matrix up to a given size as a non-sequential operation) – Lyndon White Jan 31 '15 at 12:35
8

Doing that efficiently is complex.

Wikipedia has a nice article on the subject: In-place matrix transposition with many interesting references.

A simple "follow-the-cycles" C implementation with O(1) auxiliary storage requirement (and heavily non-consecutive memory accesses) is:

/// \param[in] m input matrix
/// \param[in] h number of rows of \a m
/// \param[in] w number of columns of \a m
///
/// Performs in-place transposition of matrix \a m.
void transpose(double m[], const unsigned h, const unsigned w)
{
  for (unsigned start = 0; start <= w * h - 1; ++start)
  {
    unsigned next = start;
    unsigned i = 0;
    do
    {
      ++i;
      next = (next % h) * w + next / h;
    } while (next > start);

    if (next >= start && i != 1)
    {
      const double tmp = m[start];
      next = start;
      do
      {
        i = (next % h) * w + next / h;
        m[next] = (i == start) ? tmp : m[i];
        next = i;
      } while (next > start);
    }
  }
}

You can find a faster (C++) implementation requiring O(MN) auxiliary storage, one bit per element, here (the In-place transposition of a matrix question on Stackoverflow). Also take a look at Transpose a 1 dimensional array, that does not represent a square, in place.

PS in a number of circumstances it isn't necessary or desirable to physically reorder a matrix to its transposed ordering: it could be enough to provide options to specify that certain matrices are to be interpreted in transposed order.


Some details about the above algorithm (assuming the input matrix A(3;4) of your question):

The first chunk: (dowhile) is a sort of sequence generator:

next-sequence  start     next    i
-----------------------------------
[0]                0        0    1
[1,4,5,9,3]        1        1    5       <-
[2,8,10,7,6]       2        2    5       <-
[3,1]              3        1    1
[4,5,9,3]          4        3    3
[5,9,3]            5        3    2
[6,2]              6        2    1
[7,6]              7        6    1
[8,10,7]           8        7    2
[9,3]              9        3    1
[10,7]            10        7    1
[11]              11       11    1

Not every sequence is useful:

  • sequences of length 1 (i == 1 e.g. [0] and [11]) mean no data motion and can be skipped;
  • sequences where the final value of next is smaller than start can be skipped since they are sub-sequences of an already seen sequence.

Second chunk (if) will perform the data motion described by a sequence.

E.g. [1,4,5,9,3] means the value in position 4 goes to position 1, value in position 5 goes to position 4 … while position 1 goes to position 3 (written using the standard notation for cycles/permutations it's (1 3 9 5 4)).

About the expression:

(position % h) * w + position / h;

this is a way to convert the position between the original and the transposed matrix.

  • 1
    +1 for the suggestion to avoid the work of transposing by implementing matrix manipulation functions that transpose at point of use. This is by far the best option, and also neatly sidesteps the rather ugly code that is necessary to make C accept swapping the dimensions of a multidimensional array. – Jules Jan 31 '15 at 13:09
  • Thank you for your response. I'm having some trouble in understanding what the two chunks of code do. (the do-loop and the next if) – peperunas Feb 2 '15 at 8:43
  • I've added some notes I hope will clear things up. – manlio Feb 2 '15 at 14:54

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.