title: A Cache Efficient Matrix Transpose Program?
body: <p>So the obvious way to transpose a matrix is to use :</p>
  
  <pre><code>  for( int i = 0; i &lt; n; i++ )
  
      for( int j = 0; j &lt; n; j++ )
  
        destination[j+i*n] = source[i+j*n];
  </code></pre>
  
  <p>but I want something that will take advantage of locality and cache blocking. I was looking it up and can't find code that would do this, but I'm told it should be a very simple modification to the original. Any ideas? </p>
  
  <p>Edit: I have a 2000x2000 matrix, and I want to know how can I change the code using two <code>for</code> loops, basically splitting the matrix into blocks that I transpose individually, say 2x2 blocks, or 40x40 blocks, and see which block size is most efficient.</p>
  
  <p>Edit2: The matrices are stored in column major order, that is to say for a matrix</p>
  
  <pre><code>a1 a2    
  a3 a4
  </code></pre>
  
  <p>is stored as <code>a1 a3 a2 a4</code>.</p>