Parallel m-step preconditioners for the conjugate gradient method

To obtain an efficient parallel algorithm to solve sparse linear systems wi th the preconditioned conjugate gradient (PCG) method, two types of paralle l preconditioners are introduced. The first is a polynomial preconditioner type based on a multisplitting of the matrix system, and the second one is obtained considering only the diagonal blocks of the multisplitting, reduci ng in this case the communication cost of the algorithm. Therefore it is be tter for machines with slow communication networks. Its validity as precond itioner is justified theoretically. Indeed, the complexity of the PCG is an alyzed using the Bulk Synchronous Parallel (BSP) model. Experimental result s obtained on a IBM SP2 and a CONVEX SPP1000 using the Oxford BSP Library a re reported. (C) 1999 Elsevier Science B.V. All rights reserved.