## In-Place Matrix Transpose

I was looking around today for an algorithm for In-Place Matrix Transposition and didn’t manage to find anything, so this is what I came up with. I’ll analyze and document it fully later, but I just wanted to get it down.

It’s wasteful in that it will repeat a lot of operations, especially for “thin” matrices (worst case: vector). But it will work, never-the-less. Worst case run time is at most $O(n^2)$ where $n$ is the size of the matrix $n = rows times columns$

Edit: No longer arbitrarily repeating cycles ( was leading to identity operation, duh! ).

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 template void CMatrix::inPlaceTranspose( ) { using std::swap;   resize(cols,rows);   int i, j, k, k_start, k_new; int n = rows; int m = cols;   int length = rows*cols;   for(k_start=1; k_start < length; k_start++) { T temp = data[k_start]; bool abort = false; k_new = k = k_start;   // go through the cycle once and ensure that the starting point is // minimal do { if( k_new < k_start ) { abort = true; break; }   k = k_new; i = k%n; j = k/n; k_new = i*m + j; }while(k_new != k_start);     // if the current value is not the minimum of the cycle, then don't // perform the cycle if(abort) continue;     // otherwise, perform the cycle k_new = k = k_start; do { swap( data[k_new], temp );   k = k_new; i = k%n; j = k/n; k_new = i*m + j; }while(k_new != k_start);   swap( data[k_new], temp ); } }

And the result:

In Place Transpose

1. #1 by Rhys Ulerich on July 19, 2010 - 8:59 pm

FFTW includes this capability for square and non-square matrices, and it uses smart algorithms in either case. I wrote up the details at http://agentzlerich.blogspot.com/2010/01/using-fftw-for-in-place-matrix.html