An Application of Generalized Tree Pebbling to Sparse Matrix Factorization

DOI10.1137/0608031MaRDI QIDQ3773170zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• An Adaptive General Sparse Out-Of-Core Cholesky Factorization Scheme
• A Note on Sparse Factorization in a Paging Environment
• On Optimal Reorderings of Sparse Matrices for Parallel Cholesky Factorizations
• The design and implementation of a new out-of-core sparse cholesky factorization method
• On the storage requirement in the out-of-core multifrontal method for sparse factorization

Cites work

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

Cited in

(6)

• A survey of direct methods for sparse linear systems
• Scheduling series-parallel task graphs to minimize peak memory
• On the target pebbling conjecture
• Robust memory-aware mappings for parallel multifrontal factorizations
• Minimizing I/Os in Out-of-Core Task Tree Scheduling
• Optimal memory-aware backpropagation of deep join networks

Describes a project that uses

Uses Software

• symrcm
• TREESOLV

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3773170)