REDUCING THE EFFECT OF GLOBAL COMMUNICATION IN GMRES(M) AND CG ON PARALLEL DISTRIBUTED-MEMORY COMPUTERS

In this paper we study possibilities for the reduction of communicatio n overhead introduced by inner products in the iterative solution meth ods CG and GMRES(m). The performance of these methods on massively par allel distributed memory machines is often limited because of the glob al communication required for the inner products. We investigate two w ays of improvement. One is to assemble the results of a number of inne r products collectively. The other is to create situations where commu nication can be overlapped with computation. The matrix-vector product s may also introduce some communication overhead, but for many relevan t problems this involves only communication with a few nearby processo rs that is easily overlapped as well. So this may, but does not necess arily, further degrade the performance of the algorithm.