Parallel m-step preconditioners for the conjugate gradient method1
To obtain an efficient parallel algorithm to solve sparse linear systems with the preconditioned conjugate gradient (PCG) method, two types of parallel 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, reducing in this case the communication cost of the algorithm. Therefore it is better for machines with slow communication networks. Its validity as preconditioner is justified theoretically. Indeed, the complexity of the PCG is analyzed using the Bulk Synchronous Parallel (BSP) model. Experimental results obtained on a IBM SP2 and a CONVEX SPP1000 using the Oxford BSP Library are reported.
conjugate gradient multisplitting polynomial preconditioning bsp model