Elimination Structures for Unsymmetric Sparse $LU$ Factors

Autor:	John R. Gilbert, Joseph W. H. Liu
Rok vydání:	1993
Předmět:	MathematicsofComputing_NUMERICALANALYSIS Triangular matrix Incomplete LU factorization Incomplete Cholesky factorization LU decomposition law.invention Combinatorics symbols.namesake Gaussian elimination Factorization law symbols Analysis Cholesky decomposition Sparse matrix Mathematics
Zdroj:	SIAM Journal on Matrix Analysis and Applications. 14:334-352
ISSN:	1095-7162 0895-4798
DOI:	10.1137/0614024
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::a1e1efe7187d50441f9647d531bbd2ed https://doi.org/10.1137/0614024 Zobrazit plný text záznamu