A Krylov multisplitting algorithm for solving linear systems of equations

We consider the practical implementation of Krylov subspace methods (conjugate gradients, Gmres, etc.) for parallel computers in the case where the preconditioning matrix arises from a multisplitting. We show that the algorithm can be efficiently implemented by dividing the work into tasks that generate search directions and a single task that minimizes over the resulting subspace. Each task is assigned to a subset of processors. It is not necessary for the minimization task to send frequent information to the direction generating tasks, and this leads to high utilization with a minimum of synchronization. We study the convergence properties of various forms of the algorithm and present results of numerical examples on a sequential computer.