Composite step product methods for solving nonsymmetric linear systems

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.