Analysis of projection methods for solving linear systems with multiple right-hand sides

Tony Chan*, W. L. Wan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

95 Scopus citations

Abstract

We analyze a class of Krylov projection methods but mainly concentrate on a specific conjugate gradient (CG) implementation by Smith, Peterson, and Mittra [IEEE Transactions on Antennas and Propagation, 37 (1989), pp. 1490-1493] to solve the linear system AX = B, where A is symmetric positive definite and B is a multiple of right-hand sides. This method generates a Krylov subspace from a set of direction vectors obtained by solving one of the systems, called the seed system, by the CG method and then projects the residuals of other systems orthogonally onto the generated Krylov subspace to get the approximate solutions. The whole process is repeated with another unsolved system as a seed until all the systems are solved. We observe in practice a superconvergence behavior of the CG process of the seed system when compared with the usual CG process. We also observe that only a small number of restarts is required to solve all the systems if the right-hand sides are close to each other. These two features together make the method particularly effective. In this paper, we give theoretical proof to justify these observations. Furthermore, we combine the advantages of this method and the block CG method and propose a block extension of this single seed method.

Original languageEnglish (US)
Pages (from-to)1698-1721
Number of pages24
JournalSIAM Journal of Scientific Computing
Volume18
Issue number6
DOIs
StatePublished - Jan 1 1997

Keywords

  • Conjugate gradient method
  • Krylov space
  • Lanczos algorithm
  • Linear systems
  • Multiple right-hand sides

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Analysis of projection methods for solving linear systems with multiple right-hand sides'. Together they form a unique fingerprint.

Cite this