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 where is the size of the matrix

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 <typename T> void CMatrix<T>::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<T>( data[k_new], temp ); k = k_new; i = k%n; j = k/n; k_new = i*m + j; }while(k_new != k_start); swap<T>( data[k_new], temp ); } } |

And the result:

#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