New Parallel Symmetric SOR Preconditioners by Multi-Type Partitioning

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 if the coefficient matrix of a linear system is symmetric and positive-definite. 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 analyzed by the classic SOR theory. Numerical tests on an anisotropic model problem show that the PSSOR preconditioner can make PCG to have a faster rate of convergence and better parallel performances 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. Key words: preconditioned conjugate gradient, SSOR preconditioner, domain decomposition, multi-type partition, parallel computing MSC 2000: AMS 65Y05 (65F10)