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.