Composite step product methods for solving nonsymmetric linear systems

Tony F. Chan*, Tedd Szeto

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


First proposed in [Numer. Math., 66 (1993), pp. 295-319, Numer. Algorithms, 7 (1994), pp. 1-16] by Bank and Chan, the composite step (CS) method is a technique for curing the pivot breakdown (one of two possible breakdowns) in the biconjugate gradient (BCG) algorithm by skipping over steps in which the iterate is not defined. We show how to extend this method to cure the same breakdown inherited in product methods such as conjugate gradients squared (CGS) [SIAM J. Sci. Statist. Comput., 10 (1989), pp. 36-52], Bi-CGSTAB [SIAM J. Sci. Statist. Comput., 13 (1992), pp. 631-644], Bi-CGSTAB2 [Variants of BiCGSTAB for Matrices with Complex Spectrum, IPS Research Report No. 91-14, ETH Zürich], which are derived from a product of the BCG polynomial with another polynomial of the same degree. New methods introduced in this paper are CS-CGSTAB (composite step applied to Bi-CGSTAB) and a more stable variant of this, CS-CGSTAB2, which handles a possible additional breakdown problem due to the Bi-CGSTAB process in the case where A is skew symmetric. CS-CGSTAB2 can be viewed as an improvement over the Bi-CGSTAB(l) algorithm (Sleijpen and Fokkema [ETNA, 1 (1993), pp. 11-32]) with l = 2 in that although Bi-CGSTAB(2) is designed to cure the skew-symmetric breakdown, it does not handle pivot breakdown as CS-CGSTAB2 does. The new methods require only a minor modification to the existing product methods. Moreover, the sizes of the steps taken in our methods can vary as opposed to fixed step methods like Bi-CGSTAB(l) and Bi-CGSTAB2. Our strategy for deciding whether to skip a step does not involve any machine dependent parameters and is designed to skip near breakdowns as well as produce smoother iterates. Numerical experiments show that the new methods do produce improved performance over those without composite step on practical problems. Furthermore, we extend the "best approximation" result in [Numer. Algorithms, 7 (1994), pp. 1-16] to obtain convergence proofs for CGS and Bi-CGSTAB and their composite step stabilized versions.

Original languageEnglish (US)
Pages (from-to)1491-1508
Number of pages18
JournalSIAM Journal on Scientific Computing
Issue number6
StatePublished - Nov 1996
Externally publishedYes


  • Biconjugate gradient method
  • Breakdowns
  • Composite step
  • Lanczos method
  • Product methods

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Composite step product methods for solving nonsymmetric linear systems'. Together they form a unique fingerprint.

Cite this