On the simplification of generalized conjugate-gradient methods for nonsymmetrizable linear systems

AbstractThe conjugate-gradient (CC) method, developed by Hestenes and Stiefel in 1952, can be effectively used to solve the linear system Au = b when A is symmetrixable in the sense that ZA and Z are symmetric and positive definite (SPD) for some Z. A number of generalizations of the CG method have been proposed by the authors and by others for handling the nonsymmetrizable case. For many problems the amount of computer memory and computational effort required may be so large as to make the procedures not feasible. Truncated schemes are often used, but in some cases the truncated methods may not converge even though the nontruncated schemes converge. However, it is well known that if A is symmetric, the generalized CG schemes can be greatly simplified, even though A is not SPD, so that the truncated schemes are equivalent to the nontruncated schemes. In the present paper it is shown that such a simplification can occur if a nonsingular matrix H is available such that HA = ATH. (Of course, if A = AT, then H can be taken to be the identity matrix.) It is also shown that such an H always exists; however, it may not be practical to compute H. These results are used to derive three variations of the Lanczos method for solving nonsymmetrizable systems. Two of the forms are well known, but the third appears to be new. An argument is given for choosing the third form over the other two