Space & time efficient sparse matrix transpose

Abstract

Matrix operations are fundamental to linear algebra and have many important applications in areas such as sinmlation of physical systems, economic modeling, linear optimization and numerical analysis. One of the fundamental operations on matrices is the matrix transpose. In many linear algebra applications the matrices are extremely large and require considerable memory to store. Therefore it is desirable to transpose in-place to avoid creating a new matrix which would double the memory usage. Transposing dense matrices in-place has been studied over several decades, and many good algorithms have been found. An area that has been relatively neglected is that of in-place transpose of sparse matrices - that is, matrices where the value of most matrix elements is zero and are stored in a sparse format. The best previous algorithm requires Θ(nnz + n) time and Θ(nnz + n) additional space to transpose an n x n sparse matrix with nnz non-zero entries.