×

zbMATH — the first resource for mathematics

Evaluation of the performance of inexact GMRES. (English) Zbl 1209.65040
Summary: The inexact GMRES algorithm is a variant of the GMRES algorithm where matrix-vector products are performed inexactly, either out of necessity or deliberately, as part of a trading of accuracy for speed. Recent studies have shown that relaxing matrix-vector products in this way can be justified theoretically and experimentally. Research, so far, has focused on decreasing the workload per iteration without significantly affecting the accuracy. But relaxing the accuracy per iteration is liable to increase the number of iterations, thereby increasing the overall runtime, which could potentially end up being greater than that of the exact GMRES if there were not enough savings in the matrix-vector products.
In this paper, we assess the benefit of the inexact approach in terms of actual CPU time derived from realistic problems, and we provide cases that provide instructive insights into results affected by the build-up of the inexactness. Such information is of vital importance to practitioners who need to decide whether switching their workflow to the inexact approach is worth the effort and the risk that might come with it. Our assessment is drawn from extensive numerical experiments that gauge the effectiveness of the inexact scheme and its suitability for use in addressing certain problems, depending on how much inexactness is allowed in the matrix-vector products.

MSC:
65F10 Iterative numerical methods for linear systems
Software:
SparseMatrix
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Saad, Y.; Schultz, M.H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. sci. stat. comput., 3, 7, 856-869, (1986) · Zbl 0599.65018
[2] Bouras, A.; Fraysse, V., Inexact matrix – vector products in Krylov methods for solving linear systems: a relaxation strategy, SIAM J. matrix anal. appl., 26, 3, 660-678, (2005) · Zbl 1075.65041
[3] Eshof, J.V.D.; Sleijpen, G.L.G., Inexact Krylov subspace methods for linear systems, SIAM J. matrix anal. appl., 26, 1, 125-153, (2004) · Zbl 1079.65036
[4] Du, X.; Szyld, D.B., Inexact GMRES for singular linear systems, Bit, 48, 3, 511-531, (2008) · Zbl 1161.65024
[5] M.K. Seager, A. Greenbaum, SLAP: Sparse Linear Algebra Package, version 2, 1989, FOTRAN90 compatibility due to John Burkardt: http://people.sc.fsu.edu/ burkardt/f_src/dlap/dlap.html.
[6] Saad, Y., Iterative methods for sparse linear systems, (1996), PWS Publishing Company · Zbl 1002.65042
[7] Simoncini, V.; Szyld, D.B., Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. sci. comput., 25, 2, 454-477, (2003) · Zbl 1048.65032
[8] Giraud, L.; Gratton, S.; Langou, J., Convergence in backward error of relaxed GMRES, SIAM J. sci. comput., 29, 710-728, (2007) · Zbl 1142.65031
[9] Rémi, C.; Jocelyne, E., Newton-GMRES algorithm applied to compressible flows, Internat. J. numer. methods fluids, 23, 2, 177-190, (1996) · Zbl 0864.76057
[10] MacNamara, S.; Burrage, K.; Sidje, R.B., Inexact uniformization method for computing transient distributions of Markov chains, SIAM J. sci. comput., 29, 2562-2580, (2007) · Zbl 1154.65300
[11] T.A. Davis, Y.F. Hu, The University of Florida sparse matrix collection, ACM TOMS, 2010 (submitted for publication). http://www.cise.ufl.edu/research/sparse/matrices. · Zbl 1365.65123
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.