An Application of Generalized Tree Pebbling to Sparse Matrix Factorization

DOI10.1137/0608031zbMath0634.65015MaRDI QIDQ3773170

Joseph W. H. Liu

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

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

zbMATH Keywords

multifrontal method; elimination tree; out-of-core Cholesky factorization; pebble game for rooted trees; storage reduction; tree pebbling

Mathematics Subject Classification ID

65F50: Computational methods for sparse matrices

15A23: Factorization of matrices

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

65F05: Direct numerical methods for linear systems and matrix inversion

Related Items

A survey of direct methods for sparse linear systems, Scheduling series-parallel task graphs to minimize peak memory, Robust Memory-Aware Mappings for Parallel Multifrontal Factorizations

Uses Software

• symrcm
• TREESOLV

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The space complexity of pebble games on trees
• A comparison of two variations of a pebble game on graphs
• Black-white pebbles and graph separation
• Storage requirements for deterministic polynomial time recognizable languages
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• A compact row storage scheme for Cholesky factors using elimination trees
• On the storage requirement in the out-of-core multifrontal method for sparse factorization
• A polynomial algorithm for the min-cut linear arrangement of trees
• An Adaptive General Sparse Out-Of-Core Cholesky Factorization Scheme
• A Separator Theorem for Planar Graphs
• The Pebbling Problem is Complete in Polynomial Space
• A New Implementation of Sparse Gaussian Elimination
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• Complexity Results for Bandwidth Minimization