×

zbMATH — the first resource for mathematics

Variants of the groupwise update strategy for short-recurrence Krylov subspace methods. (English) Zbl 1368.65046
Summary: Krylov subspace methods often use short-recurrences for updating approximations and the corresponding residuals. In the bi-conjugate gradient (Bi-CG) type methods, rounding errors arising from the matrix-vector multiplications used in the recursion formulas influence the convergence speed and the maximum attainable accuracy of the approximate solutions. The strategy of a groupwise update has been proposed for improving the convergence of the Bi-CG type methods in finite-precision arithmetic. In the present paper, we analyze the influence of rounding errors on the convergence properties when using alternative recursion formulas, such as those used in the bi-conjugate residual (Bi-CR) method, which are different from those used in the Bi-CG type methods. We also propose variants of a groupwise update strategy for improving the convergence speed and the accuracy of the approximate solutions. Numerical experiments demonstrate the effectiveness of the proposed method.

MSC:
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abe, K; Sleijpen, GLG, Bicr variants of hybrid bicg methods for solving linear systems with nonsymmetric matrices, J. Comput. Appl. Math., 234, 985-994, (2010) · Zbl 1189.65058
[2] Abe, K; Sleijpen, GLG, Hybrid bi-CG methods with a bi-CG formulation closer to the IDR approach, Appl. Math. Comput., 218, 10889-10899, (2012) · Zbl 1280.65032
[3] Aihara, K; Abe, K; Ishiwata, E, A variant of idrstab with reliable update strategies for solving sparse linear systems, J. Comput. Appl. Math., 259, 244-258, (2014) · Zbl 1291.65093
[4] Davis, T.: The University of Florida Sparse Matrix Collection, http://www.cise.ufl.edu/research/sparse/matrices/ · Zbl 1365.65123
[5] Eisenstat, SC; Elman, HC; Schultz, MH, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 20, 345-357, (1983) · Zbl 0524.65019
[6] Fletcher, R, Conjugate gradient methods for indefinite systems, Lect. Notes Math., 506, 73-89, (1976) · Zbl 0326.65033
[7] Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037
[8] Greenbaum, A, Estimating the attainable accuracy of recursively computed residual methods, SIAM J. Matrix Anal. Appl., 18, 535-551, (1997) · Zbl 0873.65027
[9] Gutknecht, MH; Rozložnik, M, Residual smoothing techniques: do they improve the limiting accuracy of iterative solvers?, BIT, 41, 86-114, (2001) · Zbl 0984.65026
[10] Hestenes, MR; Stiefel, E, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49, 409-436, (1952) · Zbl 0048.09901
[11] Jiránek, P; Rozložnik, M; Gutknecht, MH, How to make simpler GMRES and GCR more stable, SIAM J. Matrix Anal. Appl., 30, 1483-1499, (2008) · Zbl 1176.65036
[12] Joubert, W, Lanczos methods for the solution of nonsymmetric systems of linear equations, SIAM J. Matrix Anal. Appl., 13, 926-943, (1992) · Zbl 0758.65026
[13] Murata, Y; Aihara, K; Abe, K; Ishiwata, E, Product-type methods with an alternative computation of the bicr coefficients, Trans. Japan. Soc. Indust. Appl. Math., 23, 417-437, (2013)
[14] Paige, CC; Saunders, MA, Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629, (1975) · Zbl 0319.65025
[15] Sleijpen, GLG; Sonneveld, P; Gijzen, MB, Bi-CGSTAB as an induced dimension reduction method, Appl. Numer. Math., 60, 1100-1114, (2010) · Zbl 1200.65024
[16] Sleijpen, GLG; Vorst, HA, Maintaining convergence properties of bicgstab methods in finite precision arithmetic, Numer. Algorithms, 10, 203-223, (1995) · Zbl 0837.65030
[17] Sleijpen, G.L.G., van der Vorst, H.A.: Reliable updated residuals in hybrid Bi-CG methods. Computing 56, 141-163 (1996) · Zbl 0842.65018
[18] Sleijpen, GLG; Vorst, HA; Fokkema, DR, Bicgstab(ℓ) and other hybrid bi-CG methods, Numer. Algorithms, 7, 75-109, (1994) · Zbl 0810.65027
[19] 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
[20] Sonneveld, P, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 10, 36-52, (1989) · Zbl 0666.65029
[21] Eshof, J; Sleijpen, GLG, Inexact Krylov subspace methods for linear systems, SIAM J. Matrix Anal. Appl., 26, 125-153, (2004) · Zbl 1079.65036
[22] Vorst, HA, Bi-CGSTAB: A fast and smoothly converging variant of bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13, 631-644, (1992) · Zbl 0761.65023
[23] Vorst, HA; Ye, Q, Residual replacement strategies for Krylov subspace iterative methods for the convergence of true residuals, SIAM J. Sci. Comput., 22, 835-852, (2000) · Zbl 0983.65039
[24] Vinsome, P.K.W.: Orthomin, an iterative method for solving sparse sets of simultaneous linear equations. In: Proc. Fourth Symposium of Reservoir Simulation, Society of Petroleum Engineers of AIME, pp. 149-159 (1976) · Zbl 1189.65058
[25] Young, DM; Jea, KC, Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods, Linear Algebra Appl., 34, 159-194, (1980) · Zbl 0463.65025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.