On Optimal Reorderings of Sparse Matrices for Parallel Cholesky Factorizations

DOI10.1137/S0895479803386354MaRDI QIDQ5317648zbMATH OpenWikidataFDO

Authors Wen-Yang Lin, Chuen-Liang Chen

Publication date 19 September 2005

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

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

zbMATH Keywords

comparison of methodselimination treefill-preserving sparse matrixJess-Kees algorithmminimum completion costnumerical examplesparallel Cholesky factorizationparallel computation

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) Parallel numerical computation (65Y05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding optimal ordering of sparse matrices for column-oriented parallel Cholesky factorization
• Minimum communication cost reordering for parallel sparse Cholesky factorization
• Reordering sparse matrices for parallel elimination
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• Independent set orderings for parallel matrix factorization by Gaussian elimination

Cited in

(25)

• Reordering sparse matrices for parallel elimination
• The average parallel complexity of Cholesky factorization
• A locally optimized reordering algorithm and its application to a parallel sparse linear system solver
• Finding optimal ordering of sparse matrices for column-oriented parallel Cholesky factorization
• Independent set orderings for parallel matrix factorization by Gaussian elimination
• Minimum communication cost reordering for parallel sparse Cholesky factorization
• An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method
• Improving parallel ordering of sparse matrices using genetic algorithms
• The multiple minimum degree ordering with greedy graph compression for vector computers
• On the minimum FLOPs problem in the sparse Cholesky factorization
• scientific article; zbMATH DE number 4131525 (Why is no real title available?)
• On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices.
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• An Application of Generalized Tree Pebbling to Sparse Matrix Factorization
• Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
• A Note on Sparse Factorization in a Paging Environment
• A Linear Reordering Algorithm for Parallel Pivoting of Chordal Graphs
• A Cartesian Parallel Nested Dissection Algorithm
• Node Selection Strategies for Bottom-Up Sparse Matrix Ordering
• Double Ordering and Fill-In for the LU Factorization
• Performance of Greedy Ordering Heuristics for Sparse Cholesky Factorization
• An optimal parallel algorithm for computing a near-optimal order of matrix multiplications
• PMORSy: parallel sparse matrix ordering software for fill-in minimization
• A survey of direct methods for sparse linear systems
• Fast and effective reordering of columns within supernodes using partition refinement

Describes a project that uses

Uses Software

• METIS

This page was built for publication: On Optimal Reorderings of Sparse Matrices for Parallel Cholesky Factorizations

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