A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization

DOI10.1137/0910070zbMath0693.65032OpenAlexW2007903522MaRDI QIDQ3468542

Barry W. Peyton, John Lewis, Alex Pothen

Publication date: 1989

Published in: SIAM Journal on Scientific and Statistical Computing (Search for Journal in Brave)

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

zbMATH Keywords

sparse matrixsparse Cholesky factorizationchordal graphcomplexity reductionclique treesparse matrix reorderingparallel direct solution

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Orthogonalization in numerical linear algebra (65F25)

Related Items

Chordal editing is fixed-parameter tractable, A clique tree algorithm for partitioning a chordal graph into transitive subgraphs, Logarithmic barriers for sparse matrix cones, Matrices with chordal inverse zero-patterns, A parallel solver for the \(hp\)-version of finite element methods, Chordal graphs and their clique graphs, Design and Implementation of a Parallel Markowitz Threshold Algorithm, Tree decomposition and discrete optimization problems: a survey, Separator orders in interval, cocomparability, and AT-free graphs, Reordering for parallelism, A survey of direct methods for sparse linear systems, On evaluating elimination tree based parallel sparse cholesky factorizations, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP, The clique-separator graph for chordal graphs, A parallel multi-\(p\) method, A practical algorithm for making filled graphs minimal, Improving parallel ordering of sparse matrices using genetic algorithms, A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph, Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution

Uses Software

• Harwell-Boeing sparse matrix collection