Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-24T12:56:44.270Z Has data issue: false hasContentIssue false
  • English
  • Français

ML(n) BiCGStab: Reformulation, Analysis and Implementation*

Published online by Cambridge University Press:  28 May 2015

Man-Chung Yeung
Man-Chung Yeung*
Affiliation:
Department of Mathematics, University of Wyoming, Laramie, WY 82071, USA
*
Corresponding author.Email address:[email protected]
Get access

Abstract

With the aid of index functions, we re-derive the ML(n)BiCGStab algorithm in [Yeung and Chan, SIAM J. Sci. Comput., 21 (1999), pp. 1263-1290] systematically. There are n ways to define the ML(n)BiCGStab residual vector. Each definition leads to a different ML(n)BiCGStab algorithm. We demonstrate this by presenting a second algorithm which requires less storage. In theory, this second algorithm serves as a bridge that connects the Lanczos-based BiCGStab and the Arnoldi-based FOM while ML(n)BiCG is a bridge connecting BiCG and FOM. We also analyze the breakdown situation from the probabilistic point of view and summarize some useful properties of ML(n)BiCGStab. Implementation issues are also addressed.

Keywords

65F1065F1565F2565F30CGSBiCGStabML(n)BiCGStabmultiple starting LanczosKrylov subspaceiterative methodslinear systems
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 5 , Issue 3 , August 2012 , pp. 447 - 492
Copyright
Copyright © Global Science Press Limited 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Dedicated to the Memory of Prof. Gene Golub. This paper was presented in Gene Golub Memorial Conference, Feb. 29-Mar. 1, 2008, at University of Massachusetts. This research was supported by 2008 Flittie Sabbatical Augmentation Award, University of Wyoming.

References

[1]Aliaga, J., Boley, D., Freund, R. and Hernández, V., A Lanczos-type method for multiple starting vectors, Math. Comp. 69 (2000), pp. 1577–1601.CrossRefGoogle Scholar
[2]Brown, P. N. and Walker, H. F., GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18(1997), pp. 37–51.CrossRefGoogle Scholar
[3]El Guennouni, A., Jbilou, K. and Sadok, H., A block version of BiCGSTAB for linear systems with multiple right-hand sides, ETNA 16 (2003), pp. 129–142.Google Scholar
[4]Fletcher, R., Conjugate Gradient Methods for Indefinite Systems, volume 506 of Lecture Notes Math., pp. 73–89. Springer-Verlag, Berlin-Heidelberg-New York, 1976.Google Scholar
[5]Gaul, A., Gutknecht, M., Liesen, J. and Nabben, R., Deflated and augmented Krylov subspace methods: basic facts and a breakdown-free deflated MINRES, Preprint, DFG Research Center Matheon, 2011.Google Scholar
[6]Gutknecht, M. H., A completed theory of the unsymmetric Lanczos process and related algorithms. Part I., SIAM J. Matrix Anal. Appl. 1992, 13:594–639.CrossRefGoogle Scholar
[7]Gutknecht, M. H., Variants of BICGStab for matrices with complex spectrum, SIAM J. Sci. Comput., 14 (1993), pp. 1020–1033.CrossRefGoogle Scholar
[8]Gutknecht, M. H., A completed theory of the unsymmetric Lanczos process and related algorithms. Part II., SIAM J. Matrix Anal. Appl. 1994, 15:15–58.CrossRefGoogle Scholar
[9]Gutknecht, M. H., Lanczos-type solvers for nonsymmetric linear systems of equations, Acta Numerica, 6 (1997), pp. 271–397.CrossRefGoogle Scholar
[10]Gutknecht, M. H., IDR Explained, ETNA 36 (2010), pp. 126–148.Google Scholar
[11]Horn, R. and Johnson, C., Matrix Analysis, Cambridge University Press, 1985.CrossRefGoogle Scholar
[12]Joubert, W. D., Generalized Conjugate Gradient and Lanczos Methods for the Solution of Non-symmetric Systems of Linear Equations, Ph.D. Thesis and Tech. Report CNA-238, Center for Numerical Analysis, University of Texas, Austin, TX, 1990.Google Scholar
[13]Gutknecht, M. H., Lanczos methods for the solution of nonsymmetric systems of linear equations, SIAM Journal on Matrix Analysis and Applications 1992; 13:926–943.Google Scholar
[14]Kaasschieter, E. F., Preconditioned conjugate gradients for solving singular systems, Journal of Computational and Applied Mathematics 1988; 24:265–275.Google Scholar
[15]Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Research Nat. Bureau of Standards, 49 (1952), pp. 33–53.CrossRefGoogle Scholar
[16]O’Leary, D., The block conjugate gradient algorithm and related methods, Linear Algebra Appl., 29(1980), pp. 293–322.CrossRefGoogle Scholar
[17]Moriya, K. and Nodera, T., Breakdown-free ML(k)BiCGStab algorithm for non-Hermitian linear systems, Gervasi, O.et al. (Eds.): ICCSA 2005, LNCS 3483, pp. 978–988, 2005.Google Scholar
[18]Reichel, L. and Ye, Q., Breakdown-free GMRES for singular systems, SIAM Journal on Matrix Analysis and Applications 2005; 26:1001–1021.CrossRefGoogle Scholar
[19]Saad, Y., The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems, SIAM Journal on Numerical Analysis, 19(1982), pp. 485–506.CrossRefGoogle Scholar
[20]Saad, Y., Iterative methods for sparse linear systems, 2nd edition, SIAM, Philadelphia, PA, 2003.Google Scholar
[21]Saad, Y. and Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856–869.CrossRefGoogle Scholar
[22]Saad, Y. and Van Der Vorst, H. A., Iterative solution of linear systems in the 20-th century, J. Comp. and Appl. Math., 123(1-2):1–33, 2000.CrossRefGoogle Scholar
[23]Sleijpen, G. L. G. and Fokkema, D. R., BiCGSTAB(l) for linear equations involving unsymmetric matrices with complex spectrum, ETNA, 1:11–32, 1993.Google Scholar
[24]Sleijpen, G. L.G., Sonneveld, P., and Van Gijzen, M. B., Bi-CGSTAB as an induced dimension reduction method, Applied Numerical Mathematics. Vol 60, pp. 1100–1114, 2010.Google Scholar
[25]Sleijpen, G. L. G. and Van Der Vorst, H. A., Maintaining convergence properties ofBiCGSTAB methods infinte precision arithmetic, Numer. Algorithms, 10 (1995), pp. 203–223.CrossRefGoogle Scholar
[26]Sleijpen, G. L. G., Reliable updated residuals in hybrid Bi-CG methods, Computing, 56 (1996), pp. 141–163.CrossRefGoogle Scholar
[27]Sleijpen, G. L. G., Van Der Vorst, H. A., and Fokkema, D. R., BiCGstab(l) and other hybrid Bi-CG methods, Numerical Algorithms, 7 (1994), pp. 75–109. Received Oct. 29, 1993.Google Scholar
[28]Sonneveld, P., CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 10 (1989), pp. 36–52.CrossRefGoogle Scholar
[29]Sonneveld, P. and Van Gijzen, M., IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems, Delft University of Technology, Reports of the Department of Applied Mathematical Analysis, Report 07–07.Google Scholar
[30]Sonneveld, P., IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems, SIAM J. Sci. Comput. Vol. 31, No. 2, pp. 1035–1062.CrossRefGoogle Scholar
[31]Van Der Vorst, H. A., Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 12 (1992), pp. 631–644.CrossRefGoogle Scholar
[32]Van Der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, Cambridge, April 2003.Google Scholar
[33]Van Der Vorst, H. and Ye, Q., Residual Replacement Strategies for Krylov Subspace Iterative Methods for the Convergence of True Residuals, SIAM J. Sci. Comput., 22 (2000):836–852.CrossRefGoogle Scholar
[34]Van Gijzen, M. and Sonneveld, P., An elegant IDR(s) variant that efficiently exploits biorthogonality properties, to appear in ACM Trans. Math. Software.Google Scholar
[35]Wei, Y. and Wu, H., Convergence properties of Krylov subspace methods for singular linear systems with arbitrary index, Journal of Computational and Applied Mathematics 2000; 114:305–318.CrossRefGoogle Scholar
[36]Wesseling, P. and Sonneveld, P., Numerical experiments with a multiple grid and a preconditioned Lanczos type method, in Approximation methods for Navier-Stokes problems (Proc. Sympos., Univ. Paderborn, Paderborn, 1979), vol. 771 of Lecture Notes in Math., Springer, Berlin, 1980, pp. 543–562.CrossRefGoogle Scholar
[37]Yeung, M., An introduction to ML(n)BiCGStab, available at http://arxiv.org/abs/1106.3678. Proceedings of Boundary Elements and Other Mesh Reduction Methods XXXIV, edited by Brebbia, & Poljak, 2012, WITpress.Google Scholar
[38]Yeung, M. and Boley, D., Transpose-free multiple Lanczos and its application in Padé approximation, Journal of Computational and Applied Mathematics, Vol 177/1 pp. 101–127, 2005.Google Scholar
[39]Yeung, M. and Chan, T., ML(k)BiCGSTAB: A BiCGSTAB variant based on multiple Lanczos starting vectors, SIAM J. Sci. Comput., Vol. 21, No. 4, pp. 1263–1290, 1999.Google Scholar
[40]Zhang, S.-L., GPBi-CG: Generalized product-type methods based on Bi-CG for solving nonsymmetric linear systems, SIAM J. Sci. Comput., 18:537–551, 1997.CrossRefGoogle Scholar