ELIMINATION STRUCTURES FOR UNSYMMETRIC SPARSE LU FACTORS

The elimination tree is central to the study of Cholesky factorization of sparse symmetric positive definite matrices. In this paper, the elimination tree is generalized to a structure appropriate for the sparse LU factorization of unsymmetric matrices. A pair of directed acyclic graphs, called elimination dags, is defined and they are used to characterize the zero-nonzero structures of the lower and upper triangular factors. These elimination structures are applied in a new algorithm to compute fill for sparse LU factorization. Experimental results indicate that the new algorithm is usually faster than earlier methods.