The Role of Elimination Trees in Sparse Factorization

DOI10.1137/0611010zbMath0697.65013OpenAlexW2077309453MaRDI QIDQ3474026

Joseph W. H. Liu

Publication date: 1990

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0611010

zbMATH Keywords

sparse matrixreorderingnumerical factorizationelimination treesCholesky factorsymbolic factorizationintersection graph representation of chordal graphslarge sparse matrix factorization

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Numerical aspects in developing LP softwares, LPAKO and LPABO, Minimal triangulations of graphs: a survey, Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs, An optimal parallel algorithm forc-vertex-ranking of trees, Vertex ranking of asteroidal triple-free graphs, Finding minimum height elimination trees for interval graphs in polynomial time, Vertex rankings of chordal graphs and weighted trees, Unnamed Item, Logarithmic barriers for sparse matrix cones, Free-surface film flow over topography: full three-dimensional finite element solutions, Analysis of a sparse hypermatrix Cholesky with fixed-sized blocking, Separators and structure prediction in sparse orthogonal factorization, The complexity of restricted star colouring, An efficient analyse phase for element problems, Acoustic inverse scattering via Helmholtz operator factorization and optimization, Solution of sparse positive definite systems on a hypercube, On the row merge tree for sparse LU factorization with partial pivoting, Constructing a minimum height elimination tree of a tree in linear time, Reordering Strategy for Blocking Optimization in Sparse Linear Solvers, Linear optimization over homogeneous matrix cones, A fast algorithm for sparse matrix computations related to inversion, On the Complexity of the Block Low-Rank Multifrontal Factorization, Forbidden graphs for tree-depth, \(l_p\)-optimal rankings and max-optimal rankings are different, Edge and pair queries-random graphs and complexity, Minimizing I/Os in Out-of-Core Task Tree Scheduling, Rankings of graphs, Fast separator decomposition for finite element meshes, Graph unique-maximum and conflict-free colorings, Enhancing Performance and Robustness of ILU Preconditioners by Blocking and Selective Transposition, Finding the edge ranking number through vertex partitions, Ordered coloring of grids and related graphs, AMPS: An Augmented Matrix Formulation for Principal Submatrix Updates with Application to Power Grids, Task scheduling for parallel sparse Cholesky factorization, On Exploiting Sparsity of Multiple Right-Hand Sides in Sparse Direct Solvers, Theww^Tfactorization of dense and sparse matrices, On the tree-depth of random graphs, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Arankings of trees, Digraph measures: Kelly decompositions, games, and orderings, State-of-the-Art Sparse Direct Solvers, Parallel QR Factorization of Block-Tridiagonal Matrices, New parallel sparse direct solvers for multicore architectures, Minimizing elimination tree height can increase fill more than linearly, Sparse Cholesky factorization on FPGA using parameterized model, Optimal vertex ranking of block graphs, Treewidth computations. I: Upper bounds, A survey of direct methods for sparse linear systems, Unnamed Item, FPGA implementation of a Cholesky algorithm for a shared-memory multiprocessor architecture, Sparse QR factorization on a massively parallel computer, Element partition trees for \(h\)-refined meshes to optimize direct solver performance. I: Dynamic programming, Combinatorial Aspects in Sparse Elimination Methods, Analysis of the solution phase of a parallel multifrontal approach, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, The complexity of bicriteria tree-depth, Hypermatrix oriented supernode amalgamation, Learning chordal extensions, The complexity of bicriteria tree-depth, Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes, Robust Memory-Aware Mappings for Parallel Multifrontal Factorizations, Fast algorithms for hierarchically semiseparable matrices, An optimal parallel algorithm for node ranking of cographs, A partial k-arboretum of graphs with bounded treewidth, Preconditioning of Linear Least Squares by Robust Incomplete Factorization for Implicitly Held Normal Equations, Ordered Coloring Grids and Related Graphs, Algorithms for generalized vertex-rankings of partial k-trees, Obstructions for Tree-depth, Refining an approximate inverse, Improving Multifrontal Methods by Means of Block Low-Rank Representations, On vertex rankings of graphs and its relatives, A parallel interior point algorithm for linear programming on a network of transputers, On the tree-depth and tree-width in heterogeneous random graphs, Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution, PCx: an interior-point code for linear programming, On constructing the elimination tree, On vertex ranking of a starlike graph, A Parallel Geometric Multifrontal Solver Using Hierarchically Semiseparable Structure, Hierarchical Orthogonal Factorization: Sparse Square Matrices