Two improved algorithms for envelope and wavefront reduction

DOI10.1007/BF02510240zbMath0891.65043MaRDI QIDQ1371664

Gary Kumfert, Alex Pothen

Publication date: 19 July 1998

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

algorithmsorderingpreconditioningfinite element methodsCholesky factorizationtest problemscombinatorial algorithmincomplete factorizationenvelope reductionlarge sparse symmetric matriceswavefront reduction

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Finite element methods applied to problems in solid mechanics (74S05) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

A variable neighborhood search and simulated annealing hybrid for the profile minimization problem, Unravelling small world networks, A Hypergraph Partitioning Model for Profile Minimization, An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method, Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming, A survey of direct methods for sparse linear systems, Multilevel hybrid spectral element ordering algorithms, An evaluation of low-cost heuristics for matrix bandwidth and profile reductions, On some properties of the Laplacian matrix revealed by the RCM algorithm, Level-based heuristics and hill climbing for the antibandwidth maximization problem, Addressing the envelope reduction of sparse matrices using a genetic programming system

Uses Software

• HSL
• MESHPART
• Harwell-Boeing sparse matrix collection
• Chaco

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal linear labelings and eigenvalues of graphs
• The effect of ordering on preconditioned conjugate gradients
• A New Algorithm for Finding a Pseudoperipheral Node in a Graph
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• An algorithm for profile and wavefront reduction of sparse matrices
• The Evolution of the Minimum Degree Ordering Algorithm
• Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms
• Ordering Methods for Preconditioned Conjugate Gradient Methods Applied to Unstructured Grid Problems
• An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
• Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse Matrices
• Laplace eigenvalues and bandwidth‐type invariants of graphs
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Geometric Mesh Partitioning: Implementation and Experiments
• Node and element resequencing using the Laplacian of a finite element graph: Part I—General concepts and algorithm
• An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• A spectral algorithm for envelope reduction of sparse matrices
• Compressed Graphs and the Minimum Degree Algorithm
• The use of profile reduction algorithms with a frontal code