Gauss elimination with supersparse matrices

An algorithm is presented which performs Gauss elimination on a very large sparse matrix. A sparse matrix is a matrix having most of its elements equal to zero. Only the non-zeroes are stored and manipulated. When the size of the sparse matrix exceeds the available main storage of the computer, it becomes necessary to partition the matrix into submatrices, which are then stored in auxiliary storage and brought to main storage only when required. Each submatrix is a sparse matrix. In addition, there are practical cases in which it is possible to define the partition in such a way that most of the submatrices will be zero matrices. When this is achieved, the submatrices are considered to be the elements of the main matrix, and the main matrix is said to be supersparse: a sparse matrix having as its elements sparse submatrices. The algorithm presented here is essentially an efficient and automatic storage management procedure, plus a set of subroutines, which can perform multiplication, transposition, addition, factorization, etc., with sparse matrices, taking full advantage of their property of being sparse. 1 table.