Analysis of the block CG method

• Date: 24. 4. 2025
• Time: 14:00 - 15:30
• Address:
  Sokolovská 83, Praha
• Room: K1
• Speaker: Petr Tichý

The Block Conjugate Gradient (BCG) algorithm was introduced by D.P. O'Leary in 1980 for solving linear systems with multiple right-hand sides. In general, block methods apply the matrix to a block of vectors instead of a single vector at each iteration. This operation is used to construct a common subspace for all right-hand sides, resulting in a richer search subspace. From a computational perspective, block methods have the potential to take advantage of the capabilities of modern computers. In this talk we recall the development of BCG algorithms. We clarify the close relationship between BCG and the block Lanczos algorithm and show how to obtain the block Jacobi matrices in BCG. This opens the door for further development, e.g., for error estimation based on (modified) block Gauss quadrature rules. Driven by the need to obtain a practical variant of the BCG algorithm that is well suited for computations in finite precision arithmetic, we also discuss some important variants of BCG due to Dubrulle. These variants avoid the difficulties with a possible rank deficiency within the block vectors.