Abstract | ||
---|---|---|
The elimination tree of a symmetric matrix plays an important role in sparse elimination. We recently defined a generalization of this structure to the unsymmetric case that retains many of its properties. Here we present an algorithm for constructing the elimination tree of an unsymmetric matrix and show how it can be used to find a symmetric reordering of the matrix into a recursive, bordered block triangular form. We also present two symbolic factorization algorithms that use the elimination tree to determine the nonzero structures of the triangular factors of such matrices. Numerical experiments demonstrate that these algorithms are efficient and compare the new symbolic factorization schemes with existing ones. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1137/050643581 | SIAM J. Matrix Analysis Applications |
Keywords | Field | DocType |
unsymmetric case,symmetric reordering,sparse elimination,symmetric matrix,sparse unsymmetric matrices,block triangular form,elimination trees,symbolic factorization algorithm,triangular factor,new symbolic factorization scheme,elimination tree,unsymmetric matrix,algorithmic aspects | Linear algebra,Algorithmics,Algebra,Matrix (mathematics),Symmetric matrix,Factorization,Tree structure,Numerical analysis,Sparse matrix,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 4 | 0895-4798 |
Citations | PageRank | References |
2 | 0.52 | 8 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stanley C. Eisenstat | 1 | 870 | 255.64 |
Joseph W. H. Liu | 2 | 829 | 217.74 |