Abstract
Recently, some novel variants of Lanczos-type methods were explored that are based on the biconjugate A-orthonormalization process. Numerical experiments coming from some physical problems indicate that these new methods are competitive with or superior to other popular Krylov subspace methods. Among them, the biconjugate A-orthogonal residual (BiCOR) method is the archetype method. However, like the biconjugate gradient (BiCG) method, the BiCOR method often shows irregular convergence behavior which can lead to numerical instability. To overcome this drawback, motivated by the effectiveness and robustness of the quasi-minimal residual (QMR) method, we derive a new QMR-like approach based on the coupled two-term biconjugate A-orthonormalization process and simple recurrences instead of the QR decomposition. Some convergence properties are given, and the special case for solving complex symmetric linear system is considered. Finally, numerical experiments are reported to illustrate the performances of our methods and their preconditioners on linear systems discretizing the Helmholtz equation or taken from Florida Sparse Matrix Collection.
Similar content being viewed by others
References
Bai, Z.: Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem. Math. Comp. 62, 209–226 (1994)
Bank, R.E., Chan, T.F.: An analysis of the composite step biconjugate gradient method. Numer. Math. 66, 295–319 (1993)
Bank, R.E., Chan, T.F.: A composite step biconjugate gradient algorithm for nonsymmetric linear systems. Numer. Algorithms 7, 1–16 (1994)
Barrett, R., Berry, M.W., Chan, T.F., Demmel, J., Donato, J.M., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., van der Vorst, H.A. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia (1996)
Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer 14, 1–137 (2005)
Brezinski, C., Redivo Zaglia, M., Sadok, H.: A breakdown-free Lanczos type algorithm for solving linear systems. Numer. Math. 63, 29–38 (1992)
Brezinski, C., Redivo Zaglia, M., Sadok, H.: New look-ahead Lanczos-type algorithms for linear systems. Numer. Math. 83, 53–85 (1999)
Bücker, H.M., Sauren, M. A parallel version of the unsymmetric Lanczos algorithm and its application to QMR. Internal Report KFA-ZAM-IB-9605. Research Centre Jülich, Germany (1996)
Carpentieri, B., Jing, Y.-F., Huang, T.-Z.: The BiCOR and CORS iterative algorithms for solving nonsymmetric linear systems. SIAM J. Sci. Comput. 33, 3020–3036 (2011)
Carpentieri, B., Jing, Y.-F., Huang, T.-Z., Pi, W.C., Sheng, X.Q.: Combining the CORS and BiCORSTAB iterative methods with MLFMA and SAI preconditioning for solving large linear systems in electromagnetics. Appl. Comput. Electromagn. Soc. (ACES) J. 27, 102–111 (2012)
Chan, T.F., Szeto, T.: Composite step product methods for nonsymmetric linear systems. SIAM J. Sci. Comput. 17, 1491–1508 (1996)
Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 25 (2011). Article 1
Erlangga, Y.A., Vuik, C., Oosterlee, C.W.: On a class of preconditioners for the Helmholtz equation. Appl. Numer. Math. 50, 409–425 (2004)
Erlangga, Y.A., Vuik, C., Oosterlee, C.W.: Comparison of multigrid and incomplete LU shifted-Laplace preconditioners for the inhomogeneous Helmholtz equation. Appl. Numer. Math. 56, 648–666 (2006)
Fletcher R. Conjugate gradient methods for indefinite systems. In: Watson, G.A. (ed.) . Numerical Analysis, Dundee, 1975. Springer, Berlin (1976). Lecture notes in mathematics, 506, pp. 73–89
Freund, R.W., Gutknecht, M.H., Nachtigal, N.M.: An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. Stat. Comput. 14, 137–158 (1993)
Freund, R.W., Nachtigal, N.M.: QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60, 315–339 (1991)
Freund, R.W., Nachtigal, N.M.: An implementation of the QMR method based on coupled two-term recurrences. SIAM J. Sci. Comput. 15(2), 313–337 (1994)
Gaul, A., Gutknecht, M.H., Liesen, J., Nabben, R.: A framework for deflated and augmented Krylov subspace methods. SIAM J. Matrix Anal. Appl. 34(2), 495–518 (2013)
Gutknecht, M.H.: The unsymmetric Lanczos algorithms and their relations to Pade approximation, continued fractions, and the qd algorithm. Preliminary Proceedings of the Copper Mountain Conference on Iterative Methods. April 1990. http://www.sam.math.ethz.ch/mhg/pub/CopperMtn90.ps.gz and CopperMtn90-7.ps.gz
Gutknecht, M.H.: Variants of BiCGSTAB for matrices with complex spectrum. SIAM J. Sci. Comput. 14, 1020–1033 (1993)
Gutknecht, M.H.: Lanczos-type solvers for nonsymmetric linear systems of equations. Acta Numer 6, 271–397 (1997)
Gutknecht, M.H., Strakoš, Z.: Accuracy of two three-term and three two-term recurrences for Krylov space solvers. SIAM J. Matrix Anal. Appl. 22, 213–229 (2000)
Gutknecht, M.H.: Deflated and augmented Krylov subspace methods: a framework for deflated BiCG and related solvers. SIAM J. Matrix Anal. Appl. 35, 1444–1466 (2014)
Jing, Y.-F., Huang, T.-Z., Zhang, Y., Li, L., Cheng G.-H., Ren, Z.-G., Duan, Y., Sogabe, T., Carpentieri, B.: Lanczos-type variants of the COCR method for complex nonsymmetric linear systems. J. Comput. Phys. 228, 6376–6394 (2009)
Jing, Y.-F., Huang, T.-Z., Carpentieri, B.: Experiments with Lanczos biconjugate A-orthonormalization methods for MoM discretizations of Maxwells equations. Prog. Electromagn. Res., PIER. 99, 427–451 (2009)
Jing, Y.-F., Huang, T.-Z., Duan, Y., Carpentieri, B.: A comparative study of iterative solutions to linear systems arising in quantum mechanics. J. Comput. Phys. 229, 8511–8520 (2010)
Jing, Y.-F., Huang, T.-Z., Carpentieri, B., Duan, Y.: Investigating the composite step biconjugate A-Orthogonal residual method for non-Hermitian dense linear systems in electromagnetics. Appl. Comput. Electromagn. Soc. (ACES) J. 27, 112–122 (2012)
Joly, P., Meurant, G.: Complex conjugate gradient methods. Numer. Algorithms 4, 379–406 (1993)
Joubert, W.D.: Generalized conjugate gradient and Lanczos methods for the solution of nonsymmetric systems of linear equations. Ph. D. Dissertation, Center for Numerical Analysis. University of Texas (1990)
Kim, S.K., Chronopoulos, A.T.: An Efficient nonsymmetric Lanczos method on parallel vector computers. J. Comput. Appl. Math. 42, 357–374 (1992)
Lanczos, C.: An Iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bur. Stand. 45, 255–282 (1950)
Lanczos, C.: Solution of linear equations by minimized iterations. J. Res. Natl. Bur. Stand. 49, 33–53 (1952)
Langtangen, H.P., Tveito, A.: A numerical comparison of conjugate gradient-like methods. Comm. Appl. Numer. Methods 4, 793–798 (1988)
Meijerink, J.A., van der Vorst, H.A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comp. 31, 148–162 (1977)
Paige, C.C., Saunders, M.A.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12, 617–629 (1975)
Parlett, B.N., Taylor, D.R., Liu, Z.A.: A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp. 44, 105–124 (1985)
Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7, 856–869 (1986)
Saad, Y.: ILUT: A dual threshold incomplete ILU factorization. Numer. Linear Algebra Appl. 1, 387–402 (1994)
Saad, Y. Iterative Methods for Sparse Linear Systems, second. SIAM, Philadelphia (2003)
Sauren, M., Bücker, H.M.: On deriving the quasi-minimal residual method. SIAM Rev. 40, 922–926 (1998)
Simoncini, V., Szyld, D.B.: Recent computational developments in Krylov subspace methods for linear systems. Numer. Linear Algebra Appl. 14, 1–59 (2007)
Sogabe, T.: Extensions of the conjugate residual method. Ph. D, Dissertation, University of Tokyo (2006)
Sogabe, T., Zhang, S.-L.: A COCR method for solving complex symmetric linear systems. J. Comput. Appl. Math. 199, 297–303 (2007)
Sogabe, T., Sugihara, M., Zhang, S.-L.: An extension of the conjugate residual method to nonsymmetric linear systems. J. Comput. Appl. Math. 226, 103–113 (2009)
Sun, D.-L., Jing, Y.-F., Huang, T.-Z., Carpentieri, B.: A quasi-minimal residual variant of the BiCORSTAB method for nonsymmetric linear systems. Comput. Math. Appl. 67, 1743–1755 (2014)
van der Vorst, H.A., Melissen, J.B.M.: A Petrov-Galerkin type method for solving Ax = b, where A is symmetric complex. IEEE Trans. Mag. 26, 706–708 (1990)
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)
Zhao, L., Huang, T.-Z.: A hybrid variant of the BiCOR method for a nonsymmetric linear system with a complex spectrum. Appl. Math. Lett. 26, 457–462 (2013)
Zhao, L., Huang, T.-Z., Jing, Y.-F., Deng, L.-J.: A generalized product-type BiCOR method and its application in signal deconvolution. Comput. Math. Appl. 66(8), 1372–1388 (2013)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, J., Dai, H. A new quasi-minimal residual method based on a biconjugate A-orthonormalization procedure and coupled two-term recurrences. Numer Algor 70, 875–896 (2015). https://doi.org/10.1007/s11075-015-9978-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-015-9978-5