Let $Ax = b$ be a large sparse nonsingular system of linear equations to be solved using Gaussian elimination with partial pivoting. The factorization obtained can be expressed in the form $A = P_1 M_1 P_2 M_2 \cdots P_{n - 1} M_{n - 1} U$, where $P_k $ is an elementary permutation matrix reflecting the row interchange that occurs at step k during the factorization, $M_k $ is a unit lower triangular matrix whose kth column contains the multipliers, and U is an upper triangular matrix.

For a general m by n sparse matrix A, a new scheme is proposed for the structural representation of the factors of its sparse orthogonal decomposition by Householder transformations. The storage scheme is row-oriented and is based on the structure of the upper triangular factor obtained in the decomposition. The storage of the orthogonal matrix factor is particularly efficient in that the overhead required is only $m + n$ items, independent of the actual number of nonzeros in the

Existing sparse partial pivoting algorithms can spend asymptotically more time manipulating data structures than doing arithmetic, although they are tuned to be efficient on many large problems. We present an algorithm to factor sparse matrices by Gaussian elimination with partial pivoting in time proportional to the number of arithmetic operations.