ELIMINATION STRUCTURES FOR UNSYMMETRIC SPARSE LU FACTORS

作     者：GILBERT, JR LIU, JWH 

作者机构：YORK UNIVDEPT COMP SCIN YORK M3J 1P3ONCANADA 

出 版 物：《SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS》 (工业与应用数学会矩阵分析和应用杂志)

年 卷 期：1993年第14卷第2期

页      面：334-352页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：SPARSE MATRIX ALGORITHMS GAUSSIAN ELIMINATION LU FACTORIZATION ELIMINATION TREE ELIMINATION DAG 

摘      要：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.