A composite step conjugate gradients squared algorithm for solving nonsymmetric linear systems

We propose a new and more stable variant of the CGS method 27] for solving nonsymmetric linear systems. The method is based on squaring the Composite Step BCG method, introduced recently by Bank and Chan 1,2], which itself is a stabilized variant of BCG in that it skips over steps for which the BCG iterate is not defined and causes one kind of breakdown in BCG. By doing this, we obtain a method (Composite Step CGS or CSCGS) which not only handles the breakdowns described above, but does so with the advantages of CGS, namely, no multiplications by the transpose matrix and a faster convergence rate than BCG. 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 method does produce improved performance over CGS on practical problems.Partially supported by the Office of Naval Research grant N00014-92-J-1890, the National Science Foundation grant ASC92-01266, and the Army Research Office grant DAAL03-91-G-150.