New parallel symmetric SOR preconditioners by multi-type partitioning

Abstract

A new parallel symmetric successive over-relaxation (PSSOR) preconditioner is proposed in this paper by the multi-type partition techniques introduced in SIAM J. Scientific Computing 20, 2006, pp. 1513–1533. In a general matrix expression, it is proved to be symmetric and positive-definite (SPD) if the coefficient matrix of a linear system is SPD. It is also proved to be equivalent to the SSOR preconditioner using the multi-type ordering. Thus, it works for the preconditioned conjugate gradient method (PCG) and can be analysed by the classic SOR theory. Numerical tests on an anisotropic model problem show that the PSSOR preconditioner can make the PCG have a faster rate of convergence and better parallel performance than the red–black SSOR preconditioner. They also confirm that the PSSOR preconditioner can have a rate of convergence that is nearly the same as the classic sequential SSOR preconditioner when the problem has large anisotropy.

Keywords:

• preconditioned conjugate gradient
• SSOR preconditioner
• domain decomposition
• multi-type partition
• parallel computing

2000 AMS Subject Classification :

• 65Y05
• 65F10

Acknowledgements

The author thanks the two anonymous referees for their valuable comments and suggestions. This project was supported by the National Science Foundation through grant DMS-0241236.