Accelerating the Conjugate Gradient Method on Distributed-Memory Computers

Abstract We present an optimised distributed-memory algorithm for the unpreconditioned conjugate gradient (CG) method. We experiment with using the CG algorithm with the compressed sparse row (CSR), compressed sparse row 5 (CSR5), compressed sparse row 2 (CSR2) and symmetric compressed sparse row (SCSR) sparse matrix formats. For the CG algorithm, we present a CSR5-based and an SCSR-based distributed-memory sparse matrix-vector multiplication (SpMV) algorithm. We developed five distributed-memory CG implementations using different combinations of the mentioned sparse matrix formats and SpMV algorithms. We benchmarked our implementations on a distributed-memory computer cluster with Intel x86-64 CPUs. For the maximum benchmarked number of compute nodes, the median performance of our optimised distributed-memory CG algorithm with CSR-based SpMV was 58 % greater than of the state-of-the-art PETSc library, and the median performance of our optimised distributed-memory CG algorithm with SCSR-based SpMV was 105 % greater than of the PETSc library.