Abstract
In many relevant large scale computations one has to solve very large linear nonsymmetric systems. Often there is no alternative but to solve these systems by some iterative solution method. In the past few years new methods have emerged that can be seen as combinations of standard Krylov subspace methods, such as Bi-CG and GMRES. One of the first hybrid schemes of this type is CGS, actually the Bi-CG squared method. Other such hybrid schemes include BiCGSTAB (a combination of Bi-CG and GMRES(1)), BiCGSTAB(ℓ) (Bi-CG combined with GMRES(ℓ)), and the nested GMRESR method (GMRES preconditioned by itself or other schemes). These methods have been successful in solving relevant sparse nonsymmetric linear systems.
After a presentation of some recent methods we will discuss briefly implementation issues of the Krylov subspace methods, including possibilities for distributed parallel computation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
O. Axelsson and P. S. Vassilevski, A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning, SIAM J. Matrix Anal. Appl., 12(4):625–644, 1991.
R. Bank and T. F. Chan, A composite step Bi-Conjugate Gradient algorithm for nonsymmetric linear systems, to appear.
R. Barrett, M. Berry, T. Chan, J. Demmel, J. Dunato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine and H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1993.
G. C. Crone and H. A. van der Vorst, Communication aspects of the Conjugate Gradient method on distributed memory machines, submitted to Supercomputer.
E. de Sturler and D. R. Fokkema, Nested Krylov methods and preserving the orthogonality, Technical Report Preprint 796, Utrecht University, Utrecht, 1993.
E. de Sturler and H. A. van der Vorst, Reducing the effect of global communication in GMRES(m) and CG on parallel distributed memory computers, Technical Report Preprint 832, Utrecht University, Utrecht, 1993.
J. J. Dongarra, I. S. Duff, D. C. Sorensen, and H. A. van der Vorst, Solving linear systems on vector and shared memory computers, SIAM, Philadelphia, 1991.
I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse Matrix Test Problems, ACM Trans. on Math. Softw., 15:1–14, 1989.
S. C. Eisenstat, H. C. Elman, and M. H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 20:345–357, 1983.
R. Fletcher, Conjugate gradient methods for indefinite systems, volume 506 of Lecture Notes Math., pages 73–89, Springer-Verlag, Berlin-Heidelberg-New York, 1976.
R. W. Freund and N. M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Num. Math., 60:315–339, 1991.
M. H. Gutknecht, Variants of BICGSTAB for matrices with complex spectrum, SIAM J. Sci. Comput., 14:1020–1033, 1993.
C. Lanczos, Solution of systems of linear equations by minimized iterations, J. Res. Natl. Bur. Stand, 49:33–53, 1952.
Claude Pommerell, Solution of large unsymmetric systems of linear equations, PhD thesis, Swiss Federal Institute of Technology, Zürich, 1992.
Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14:461–469, 1993.
Y. Saad and M. H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7:856–869, 1986.
G. L. G. Sleijpen and D. R. Fokkema, Bi-CGSTAB(ℓ) for linear equations involving unsymmetric matrices with complex spectrum, ETNA, 1:11–32, 1993.
G. L. G. Sleijpen, D. R. Fokkema and H. A. van der Vorst, BiCGstab(ℓ) and other hybrid Bi-CG methods, to appear in Numerical Algorithms.
P. Sonneveld, CGS: a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 10:36–52, 1989.
A. van der Sluis and H. A. van der Vorst, SIRT-and CG-type methods for the iterative solution of sparse linear least-squares problems, Lin. Alg. and its Appl., 130:257–302, 1990.
H. A. van der Vorst, The convergence behaviour of preconditioned CG and CG-S in the presence of rounding errors, In: O. Axelsson and L. Yu. Kolotilina, editors, Preconditioned Conjugate Gradient Methods, Berlin, 1990. Springer Verlag. Lecture Notes in Mathematics 1457.
H. A. van der Vorst, Conjugate gradient type methods for nonsymmetric linear systems, In: R. Beauwens and P. de Groen, editors, Iterative Methods in Linear Algebra, Amsterdam, 1992, North-Holland.
H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of non-symmetric linear systems, SIAM J. Sci. Statist. Comput., 13:631–644, 1992.
H. A. van der Vorst and C. Vuik, GMRESR: A family of nested GMRES methods, Technical Report 91-80, Delft University of Technology, Faculty of Tech. Math., 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Van der Vorst, H.A. (1994). Recent developments in hybrid CG methods. In: Gentzsch, W., Harms, U. (eds) High-Performance Computing and Networking. HPCN-Europe 1994. Lecture Notes in Computer Science, vol 797. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57981-8_113
Download citation
DOI: https://doi.org/10.1007/3-540-57981-8_113
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57981-6
Online ISBN: 978-3-540-48408-0
eBook Packages: Springer Book Archive