Improving communication in conjugate gradient solvers using regularized variable s-step approach for solving linear system of equations

Abstract

The signal (or image) recovery problem typically involves solving a linear system with one or multiple right-hand sides. In this paper, we propose algorithms for addressing these types of linear systems.

The conjugate gradient (CG) method is widely utilized to solve symmetric positive definite (SPD) linear systems arising from signal problems. Communication significantly impacts the performance of this algorithm. To address this issue, this paper presents algorithms aimed at reducing communication while solving linear systems with single and multiple right-hand sides, utilizing both CG and cooperative CG algorithms. Subsequently, the performance of the proposed algorithms was enhanced by employing techniques such as varying the parameter $s$ in $s$-step algorithms and adjusting the parameters in regularization. Finally, the results of these algorithms and the effectiveness of the techniques used were demonstrated through several numerical examples.