A breakdown-free block conjugate gradient method (Q2359753)

The paper deals with the block conjugate gradient (BCG) method for solving large and sparse linear systems \[ AX=B, \] where \(A\in \mathbb{R}^{n\times n}\) is a symmetric, positive definite system matrix, \(B\in \mathbb{R}^{n\times s}\), \(s\geq 1\), is a matrix containing multiple right-hand sides, and \(X\in \mathbb{R}^{n\times s}\) represents a solution. At first, the standard BCG method is revisited and all possible situations of rank deficiency that cause breakdown are discussed. Then, the breakdown free block conjugate gradient (BFBCG) algorithm is proposed and analyzed. The algorithm uses the matrix operation \(\operatorname{orth}(\cdot)\) extracting an orthogonal basis from the search space. This operation can be implemented by the QR decomposition with column pivoting. It is proved that the breakdowns are avoided and the convergence analysis is presented. BFBCG yields faster convergence than the restarting BCG. Numerical experiments demonstrate the robustness of BFBCG on several different examples. The paper concludes with a wide discussion of relation to other work. The paper is well written and easy to understand.