A new quasi-minimal residual method based on a biconjugate \(A\)-orthonormalization procedure and coupled two-term recurrences. (English) Zbl 1332.65046
Summary: 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.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
Keywords:
complex non-Hermitian matrices; coupled two-term recurrences; complex symmetric matrices; comparison of methods; algorithm; finite difference method; Lanczos-type methods; Krylov subspace methods; biconjugate \(A\)-orthogonal residual method; biconjugate gradient method; numerical instability; quasi-minimal residual method; convergence; numerical experiment; preconditioner; Helmholtz equationReferences:
| [1] | Bai, Z.: Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem. Math. Comp. 62, 209-226 (1994) · Zbl 0809.65029 · doi:10.1090/S0025-5718-1994-1201066-7 |
| [2] | Bank, R.E., Chan, T.F.: An analysis of the composite step biconjugate gradient method. Numer. Math. 66, 295-319 (1993) · Zbl 0802.65038 · doi:10.1007/BF01385699 |
| [3] | Bank, R.E., Chan, T.F.: A composite step biconjugate gradient algorithm for nonsymmetric linear systems. Numer. Algorithms 7, 1-16 (1994) · Zbl 0809.65025 · doi:10.1007/BF02141258 |
| [4] | 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) · Zbl 0814.65030 |
| [5] | Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer 14, 1-137 (2005) · Zbl 1115.65034 · doi:10.1017/S0962492904000212 |
| [6] | Brezinski, C., Redivo Zaglia, M., Sadok, H.: A breakdown-free Lanczos type algorithm for solving linear systems. Numer. Math. 63, 29-38 (1992) · Zbl 0739.65027 · doi:10.1007/BF01385846 |
| [7] | Brezinski, C., Redivo Zaglia, M., Sadok, H.: New look-ahead Lanczos-type algorithms for linear systems. Numer. Math. 83, 53-85 (1999) · Zbl 0932.65040 · doi:10.1007/s002110050439 |
| [8] | 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) |
| [9] | 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) · Zbl 1251.65045 · doi:10.1137/100794031 |
| [10] | 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) |
| [11] | Chan, T.F., Szeto, T.: Composite step product methods for nonsymmetric linear systems. SIAM J. Sci. Comput. 17, 1491-1508 (1996) · Zbl 0862.65018 · doi:10.1137/S1064827594269202 |
| [12] | Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 25 (2011). Article 1 · Zbl 1365.65123 |
| [13] | Erlangga, Y.A., Vuik, C., Oosterlee, C.W.: On a class of preconditioners for the Helmholtz equation. Appl. Numer. Math. 50, 409-425 (2004) · Zbl 1051.65101 · doi:10.1016/j.apnum.2004.01.009 |
| [14] | 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) · Zbl 1094.65041 · doi:10.1016/j.apnum.2005.04.039 |
| [15] | 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 · Zbl 1200.65022 |
| [16] | 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) · Zbl 0770.65022 · doi:10.1137/0914009 |
| [17] | Freund, R.W., Nachtigal, N.M.: QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60, 315-339 (1991) · Zbl 0754.65034 · doi:10.1007/BF01385726 |
| [18] | 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) · Zbl 0803.65036 · doi:10.1137/0915022 |
| [19] | 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) · Zbl 1273.65049 · doi:10.1137/110820713 |
| [20] | 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 · Zbl 1273.65049 |
| [21] | Gutknecht, M.H.: Variants of BiCGSTAB for matrices with complex spectrum. SIAM J. Sci. Comput. 14, 1020-1033 (1993) · Zbl 0837.65031 · doi:10.1137/0914062 |
| [22] | Gutknecht, M.H.: Lanczos-type solvers for nonsymmetric linear systems of equations. Acta Numer 6, 271-397 (1997) · Zbl 0888.65030 · doi:10.1017/S0962492900002737 |
| [23] | 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) · Zbl 0976.65030 · doi:10.1137/S0895479897331862 |
| [24] | 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) · Zbl 1316.65041 · doi:10.1137/130923087 |
| [25] | 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) · Zbl 1173.65316 · doi:10.1016/j.jcp.2009.05.022 |
| [26] | 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) · doi:10.2528/PIER09101901 |
| [27] | 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) · Zbl 1200.65022 · doi:10.1016/j.jcp.2010.07.034 |
| [28] | 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) |
| [29] | Joly, P., Meurant, G.: Complex conjugate gradient methods. Numer. Algorithms 4, 379-406 (1993) · Zbl 0780.65021 · doi:10.1007/BF02145754 |
| [30] | 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) · Zbl 0913.65029 |
| [31] | Kim, S.K., Chronopoulos, A.T.: An Efficient nonsymmetric Lanczos method on parallel vector computers. J. Comput. Appl. Math. 42, 357-374 (1992) · Zbl 0756.65057 · doi:10.1016/0377-0427(92)90085-C |
| [32] | 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) · doi:10.6028/jres.045.026 |
| [33] | Lanczos, C.: Solution of linear equations by minimized iterations. J. Res. Natl. Bur. Stand. 49, 33-53 (1952) · doi:10.6028/jres.049.006 |
| [34] | Langtangen, H.P., Tveito, A.: A numerical comparison of conjugate gradient-like methods. Comm. Appl. Numer. Methods 4, 793-798 (1988) · Zbl 0659.65032 · doi:10.1002/cnm.1630040613 |
| [35] | 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) · Zbl 0349.65020 |
| [36] | Paige, C.C., Saunders, M.A.: Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal. 12, 617-629 (1975) · Zbl 0319.65025 · doi:10.1137/0712047 |
| [37] | Parlett, B.N., Taylor, D.R., Liu, Z.A.: A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp. 44, 105-124 (1985) · Zbl 0564.65022 |
| [38] | 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) · Zbl 0599.65018 · doi:10.1137/0907058 |
| [39] | Saad, Y.: ILUT: A dual threshold incomplete ILU factorization. Numer. Linear Algebra Appl. 1, 387-402 (1994) · Zbl 0838.65026 · doi:10.1002/nla.1680010405 |
| [40] | Saad, Y. Iterative Methods for Sparse Linear Systems, second. SIAM, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [41] | Sauren, M., Bücker, H.M.: On deriving the quasi-minimal residual method. SIAM Rev. 40, 922-926 (1998) · Zbl 0913.65029 · doi:10.1137/S0036144596319368 |
| [42] | Simoncini, V., Szyld, D.B.: Recent computational developments in Krylov subspace methods for linear systems. Numer. Linear Algebra Appl. 14, 1-59 (2007) · Zbl 1199.65112 · doi:10.1002/nla.499 |
| [43] | Sogabe, T.: Extensions of the conjugate residual method. Ph. D, Dissertation, University of Tokyo (2006) · Zbl 1367.65053 |
| [44] | Sogabe, T., Zhang, S.-L.: A COCR method for solving complex symmetric linear systems. J. Comput. Appl. Math. 199, 297-303 (2007) · Zbl 1108.65028 · doi:10.1016/j.cam.2005.07.032 |
| [45] | 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) · Zbl 1170.65026 · doi:10.1016/j.cam.2008.05.018 |
| [46] | 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) · Zbl 1367.65053 · doi:10.1016/j.camwa.2014.04.014 |
| [47] | 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) · doi:10.1109/20.106415 |
| [48] | 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) · Zbl 0872.65023 · doi:10.1137/S1064827592236313 |
| [49] | 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) · Zbl 1261.65036 · doi:10.1016/j.aml.2012.11.008 |
| [50] | 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) · Zbl 1350.65027 · doi:10.1016/j.camwa.2013.08.007 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
