On Block Elimination for Sparse Linear Systems
Alan D. George · SIAM Journal on Numerical Analysis · 1974
We consider the solution of linear equations involving a sparse coefficient matrix having a triangular factorization. In addition to the usual triangular factorization, we consider block factorizations, where the diagonal blocks of the factors are not necessarily triangular. We show that under certain sparsity conditions, these alternate factorizations may require fewer arithmetic operations and less storage. In particular, we obtain the surprising result that it may be beneficial to compute an unsymmetric factorization of a symmetric matrix.