The search functionality is under construction.

The search functionality is under construction.

In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently *serial*. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order *N*, where *N* is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of *independent sets* and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are *real positive*, i.e., their real parts of the eigenvalues are positive. We have used GMRES(*m*) as our outer iterative method, so that the convergence of GMRES(*m*) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2578-2587

- Publication Date
- 2008/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1093/ietfec/e91-a.9.2578

- Type of Manuscript
- PAPER

- Category
- Numerical Analysis and Optimization

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Sangback MA, "A Performance Comparison of the Parallel Preconditioners for Iterative Methods for Large Sparse Linear Systems Arising from Partial Differential Equations on Structured Grids" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2578-2587, September 2008, doi: 10.1093/ietfec/e91-a.9.2578.

Abstract: In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently *serial*. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order *N*, where *N* is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of *independent sets* and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are *real positive*, i.e., their real parts of the eigenvalues are positive. We have used GMRES(*m*) as our outer iterative method, so that the convergence of GMRES(*m*) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2578/_p

Copy

@ARTICLE{e91-a_9_2578,

author={Sangback MA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A Performance Comparison of the Parallel Preconditioners for Iterative Methods for Large Sparse Linear Systems Arising from Partial Differential Equations on Structured Grids},

year={2008},

volume={E91-A},

number={9},

pages={2578-2587},

abstract={In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently *serial*. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order *N*, where *N* is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of *independent sets* and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are *real positive*, i.e., their real parts of the eigenvalues are positive. We have used GMRES(*m*) as our outer iterative method, so that the convergence of GMRES(*m*) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.},

keywords={},

doi={10.1093/ietfec/e91-a.9.2578},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - A Performance Comparison of the Parallel Preconditioners for Iterative Methods for Large Sparse Linear Systems Arising from Partial Differential Equations on Structured Grids

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2578

EP - 2587

AU - Sangback MA

PY - 2008

DO - 10.1093/ietfec/e91-a.9.2578

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E91-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2008

AB - In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently *serial*. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order *N*, where *N* is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of *independent sets* and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are *real positive*, i.e., their real parts of the eigenvalues are positive. We have used GMRES(*m*) as our outer iterative method, so that the convergence of GMRES(*m*) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.

ER -