A Data Structure for Sparse $QR$ and $LU$ Factorizations

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 factor. The same scheme is applicable to sparse orthogonal factorization by Givens rotations, and also to the recent implementation of sparse Gaussian elimination with partial pivoting developed by George and Ng (this Journal, 1987, to appear). Experimental results are provided to compare the sparse Gaussian elimination using the new storage scheme with that proposed by George and Ng.