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

elimination treemultifrontal methodout-of-core Cholesky factorizationpebble game for rooted treesstorage reductiontree pebbling

Mathematics Subject Classification ID

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

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

• A compact row storage scheme for Cholesky factors using elimination trees
• A comparison of two variations of a pebble game on graphs
• A New Implementation of Sparse Gaussian Elimination
• A polynomial algorithm for the min-cut linear arrangement of trees
• A Separator Theorem for Planar Graphs
• 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
• 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?)
• 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)

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

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)