On General Row Merging Schemes for Sparse Givens Transformations
Joseph W. H. Liu · SIAM Journal on Scientific and Statistical Computing · 1986
This paper introduces general row merging schemes for the $QR$ decomposition of sparse matrices by Givens rotations. They can be viewed as a generalization of row rotations to submatrix rotations (or merging) in the recent method by George and Heath [12]. Based on the column ordering and the structure of the given sparse matrix, we present an algorithm to determine automatically a sequence of submatrix rotations appropriate for sparse decomposition. It is shown that the actual numerical computation can be organized as a sequence of reductions of two upper trapezoidal full submatrices into another upper trapezoidal full matrix. Experimental results are provided to compare the practical performance of the proposed method and the George-Heath scheme. Significant reduction in arithmetic operations and factorization time is achieved in exchange for a very modest increase in working storage. The interpretation of general row merging as a special variable row pivoting method is also presented.