Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution

DOI10.1016/0024-3795(93)90248-MzbMath0786.05081MaRDI QIDQ1311330

Alex Pothen, Xiaoqing Yuan, Barry W. Peyton

Publication date: 26 January 1994

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

chordal graphlinear time algorithmparallel computersperfect elimination orderingCholesky factorsparse triangular systems

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A clique tree algorithm for partitioning a chordal graph into transitive subgraphs, Partial inversion for linear systems and partial closure of independence graphs, A survey of direct methods for sparse linear systems, A new efficient algorithm for computing Gröbner bases \((F_4)\), The impact of high-performance computing in the solution of linear systems: Trends and problems

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Some aspects of perfect elimination orderings in chordal graphs
• Reordering sparse matrices for parallel elimination
• A clique tree algorithm for partitioning a chordal graph into transitive subgraphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• The Role of Elimination Trees in Sparse Factorization
• The Evolution of the Minimum Degree Ordering Algorithm
• A Linear Reordering Algorithm for Parallel Pivoting of Chordal Graphs
• A Fast Reordering Algorithm for Parallel Sparse Triangular Solution
• Stability of the Partitioned Inverse Method for Parallel Solution of Sparse Triangular Systems
• Optimal Parallel Solution of Sparse Triangular Systems