An Application of Generalized Tree Pebbling to Sparse Matrix Factorization

DOI10.1137/0608031zbMath0634.65015OpenAlexW2121964667MaRDI 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 methodelimination treeout-of-core Cholesky factorizationpebble game for rooted treesstorage reductiontree pebbling

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (5)

Scheduling series-parallel task graphs to minimize peak memory ⋮ Minimizing I/Os in Out-of-Core Task Tree Scheduling ⋮ A survey of direct methods for sparse linear systems ⋮ Robust Memory-Aware Mappings for Parallel Multifrontal Factorizations ⋮ Optimal memory-aware backpropagation of deep join networks

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

This page was built for publication: An Application of Generalized Tree Pebbling to Sparse Matrix Factorization