Performance evaluation of a new parallel preconditioner
Published 19 November 2002
Keith Gremban, Gary L. Miller, Marco Zagha
Citations41
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new class of preconditioners is developed that is based on the connectivity of the graphs corresponding to the matrices and are well-structured for parallel implementation, and outperform both diagonal scaling and incomplete Cholesky preconditionsers.
Abstract
The linear systems associated with large, sparse, symmetric, positive definite matrices are often solved iteratively using the preconditioned conjugate gradient method. We have developed a new class of preconditioners, support tree preconditioners, that are based on the connectivity of the graphs corresponding to the matrices and are well-structured for parallel implementation. We evaluate the performance of support tree preconditioners by comparing them against two common types of preconditioners: diagonal scaling and incomplete Cholesky. Support tree preconditioners require less overall storage and less work per iteration than incomplete Cholesky preconditioners. In terms of total execution time, support tree preconditioners outperform both diagonal scaling and incomplete Cholesky preconditioners.>
Keywords
Computer ScienceMaterials Science
The Carus mathematical monographsRandom Walks and Electric Networks
1,776 Citations1984Peter G. Doyle, J. Laurie Snell
SIAM Journal on Matrix Analysis and ApplicationsPartitioning Sparse Matrices with Eigenvectors of Graphs
1,692 Citations1990Alex Pothen, Horst D. Simon +1 more
It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph, which can be used to compute good separators in grid graphs.
Mathematics of ComputationAn iterative solution method for linear systems of which the coefficient matrix is a symmetric 𝑀-matrix
1,412 Citations1977J. A. Meijerink, H.A. van der Vorst
A particular class of regular splittings of not necessarily symmetric M-matrices is proposed, if the matrix is symmetric, this splitting is combined with the conjugate-gradient method to provide a fast iterative solution algorithm.
Computing Systems in EngineeringPartitioning of unstructured problems for parallel processing
723 Citations1991Horst D. Simon
Numerical comparisons on large-scale two- and three-dimensional problems demonstrate the superiority of the new spectral bisection algorithm.
SIAM Journal on Scientific ComputingAn Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
485 Citations1995Bruce Hendrickson, Robert W. Leland
A new domain mapping algorithm is presented that extends recent work in which ideas from spectral graph theory have been applied to this problem and provides better decompositions arrived at more economically and robustly than with previous spectral methods.
Mathematics of ComputationSolving Linear Systems on Vector and Shared Memory Computers.
438 Citations1992James M. Ortega, Jack Dongarra +3 more
Vector and parallel processing overview of current high-performance computers implementation details and overhead performance - analysis, modeling and measurements building blocks in linear algebra direct solution of sparse linear systems iterative solution of dense linear systems.
BIT Numerical MathematicsThe effect of ordering on preconditioned conjugate gradients
353 Citations1989Iain Duff, Gérard Meurant
It is shown empirically that there can be a significant difference in the number of iterations required by the conjugate gradient method and reasons for this marked difference in performance are suggested.
SIAM Journal on Scientific and Statistical ComputingEfficient Implementation of a Class of Preconditioned Conjugate Gradient Methods
315 Citations1981Stanley C. Eisenstat
The preconditioned conjugate gradient (PCG) method is an effective means for solving systems of linear equations where the coefficient matrix is symmetric and positive definite.
International Journal of High Speed ComputingSOLVING SPARSE TRIANGULAR LINEAR SYSTEMS ON PARALLEL COMPUTERS
179 Citations1989E. Anderson, Yousef Saad
This paper describes and compares three parallel algorithms for solving sparse triangular systems of equations and considers both row-wise and jagged diagonal storage for the offdiagonal blocks.
SIAM Journal on Scientific and Statistical ComputingHigh Performance Preconditioning
151 Citations1989H.A. van der Vorst
It is shown how a rather high performance can be achieved for the more effective preconditioners, such as successive over-relaxation and incomplete decompositions, on most vector computers if used in a straightforward manner.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors
75 Citations1993Guy E. Blelloch, Michael A. Heroux +1 more
SIAM Journal on Matrix Analysis and ApplicationsStopping Criteria for Iterative Solvers
65 Citations1992Mario Arioli, Iain Duff +1 more
This paper shows how a theory for backward error analysis can be used to derive a family of stopping criteria for iterative methods and considers particular members of this family.
SIAM Journal on Scientific ComputingOptimal Parallel Solution of Sparse Triangular Systems
60 Citations1993F.L. Alvarado, Robert Schreiber
The parallel solution of a sparse system Lx = b with triangular matrix L is considered, which is often a performance bottleneck in parallel computation, and the inverse of L is represented as a product of a few sparse factors.
The IMA volumes in mathematics and its applicationsAutomatic Mesh Partitioning
58 Citations1993Gary L. Miller, Shang‐Hua Teng +2 more
An efficient approach to partitioning unstructured meshes that occur naturally in the finite element and finite difference methods that makes use of the underlying geometric structure of a given mesh and finds a provably good partition in random O(n) time is described.
Computer Physics CommunicationsICCG and related methods for 3D problems on vector computers
43 Citations1989H.A. van der Vorst
This paper considers also techniques that lead to larger vector lengths in the critical part of the ICCG preconditioning for 3D problems, and results, obtained on Japanese supercomputers, are reported.
Performance evaluation of a new parallel preconditioner
41 Citations2002Keith Gremban, Gary L. Miller +1 more
A new class of preconditioners is developed that is based on the connectivity of the graphs corresponding to the matrices and are well-structured for parallel implementation, and outperform both diagonal scaling and incomplete Cholesky preconditionsers.
Applied Numerical MathematicsA parallel preconditioned conjugate gradient package for solving sparse linear systems on a Cray Y-MP
27 Citations1991Michael A. Heroux, Phuong Vu +1 more
Current activities at Cray Research to develop general-purpose, production-quality software for the efficient solution of sparse linear systems are discussed, including the development of a package of iterative methods that includes conjugate gradient and related methods along with several preconditioners.
Numerische MathematikComparison of linear system solvers applied to diffusion-type finite element equations
11 Citations1989Anne Greenbaum, Congming Li +1 more
Various iterative methods for solving the linear systems associated with finite element approximations to self-adjoint elliptic differential operators are compared and the hierarchical basis function idea is shown to be especially effective on both serial and parallel architectures.
Automatic partitioning of unstructured grids into connected components
5 Citations1993Leonardo Dagum
Two partitioning schemes that guarantee connected components given a connected initial grid are presented and comparison results from a number of two and three dimensional unstructured grids are presented.
Multilevel preconditioners: analysis, performance enhancements and parallel algorithms
2 Citations1992Xian-Zhong Guo
A grid-generation strategy is developed that relates the multilevel preconditioners to the underlying operator, and it is demonstrated that this strategy is effective in terms of both iteration counts and elapsed time.