Finding the transpose of a very, very large matrix

Question

I have this huge 2 dimensional array of data. It is stored in row order:

A(1,1) A(1,2) A(1,3) ..... A(n-2,n) A(n-1,n) A(n,n)

I want to rearrange it into column order

A(1,1) A(2,1) A(3,1) ..... A(n,n-2) A(n,n-1) A(n,n)

The data set is rather large - more than will fit on the RAM on a computer. (n is about 10,000, but each data item takes about 1K of space.)

Does anyone know slick or efficient algorithms to do this?

Answer 1

Create n empty files (reserve enough space for n elements, if you can). Iterate through your original matrix. Append element (i,j) to file j. Once you are done with that, append the files you just wrote.