Synchronization-reducing variants of the biconjugate gradient and the quasi-minimal residual methods.

Keywords

Authors

Abstract

The Biconjugate Gradient (BiCG) and the QuasiMinimal Residual (QMR) method are among the popular iterative methods for the solution of large, sparse, nonsymmetric systems of linear equations. When these methods are implemented on largescale parallel computers, their scalability is limited by the synchronization caused when carrying out inner productlike operations. Therefore, we propose two new synchronizationreducing variants of BiCG and QMR in an attempt to mitigate these negative performance effects. The idea behind these new sstep variants is to group several dot products for joint execution. Although these new algorithms still reveal numerical instabilities, they are shown to keep the cost of inner productlike operations almost independent of the number of processes, thus improving scalability significantly.