Additive polynomial preconditions for parallel computers (Q1118974)

The linear system \(Kx=f\) with a symmetric and positive definite matrix K (arising f.i. from the discretization of elliptic partial differential equations) can be solved by the preconditioned conjugate gradient method. The aim in constructing preconditioners for parallel computers is to choose a matrix M so that the eigenvalues of \(M^{-1}K\) are close to unity and for which the system \(Ms=r\) is easy to implement on parallel computers. Polynomial preconditioners are derived by splitting the matrix \(K=P-Q\) and taking m steps of the iterative method described by \(G=P^{- 1}Q\) towards the solution of \(Ks=r\) with \(s^ 0=0.\) The authors compare the symmetric successive overrelaxation (SSOR) iteration for G with additive SOR-methods. They give conditions for the additive preconditioners to be symmetric and positive definite. The optimal relaxation parameter \(\omega\) is derived when the two operators are the forward and backward SOR operators for 2-cyclic matrices. For the usual Laplace model problem they show that the SOR-additive method used as a standalone method is twice as fast as the SSOR method and is as effective as the SSOR method in reducing the condition number of K. The parallel implementation of the methods on a system of multiple vector processors connected to a shared memory and on a message passing scalar processor environment with local memory is discussed. The effectiveness of different subdivisions and multi-coloring is considered. Communication and arithmetic operations per iteration are counted and test results on the Blue Chip emulator are presented. One conclusion is that for both implementations SSOR is preferable to SOR-additive if the same number of processors are used for both methods.