Abstract
It is well known that the FGMRES algorithm can be used as an alternative to iterative refinement and, in some instances, is successful in computing a backward stable solution when iterative refinement fails to converge. In this study, we analyse how variants of the Chebyshev algorithm can also be used to accelerate iterative refinement without loss of numerical stability and at a computational cost at each iteration that is less than that of FGMRES and only marginally greater than that of iterative refinement. A component-wise error analysis of the procedure is presented and numerical tests on selected sparse test problems are used to corroborate the theory.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arioli, M., Demmel, J.W., Duff, I.S.: Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Appl. 10(2), 165–190 (1989)
Arioli, M., Duff, I.S.: Using FGMRES to obtain backward stability in mixed-precision. Electron. Trans. Numer. Anal. 33, 31–44 (2009)
Arioli, M., Duff, I.S., Gratton, S., Pralet, S.: A note on GMRES preconditioned by a perturbed LDL T-decomposition with static pivoting. SIAM J. Sci. Comput. 29, 2024–2044 (2007)
Brown, R.F.: A Topological introduction to nonlinear analysis. Birkhauser, Boston (1993)
Davis, T.A., Hu, Y.: The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw. 38(1), 1–25 (2011)
Golub, G.H., Loan, C.F.V.: Matrix computations, 2nd edn. Johns Hopkins University Press, Baltimore (1989)
Gutknecht, M.H., Röllin, S.: The Chebyshev iteration revisited. Parallel Comput. 28, 263–283 (2002)
Gutknecht, M.H., Strakoš, Z.: Accuracy of two three-term and three two-term recurrences for Krylov space solvers. SIAM J. Matrix Anal. Appl. 21(1), 213–229 (2000)
Hageman, L.A., Young, D.M.: Applied iterative methods. Academic Press, New York (1981)
Higham, N.J.: Accuracy and stability of numerical algorithms, 2nd Edition. Society for Industrial and Applied Mathematics, Philadelphia (2002)
Hogg, J.D., Scott, J.A.: A fast and robust mixed precision solver for the solution of sparse symmetric linear systems. ACM Trans. Math. Softw. 37, 17–24 (2010)
Hogg, J.D., Scott, J.A.: A note on the solve phase of a multicore solver. Tech. Rep. RAL-TR-2010-007, Rutherford Appleton Laboratory (2010)
Hogg, J.D., Scott, J.A.: HSL_MA97: A bit-compatible multifrontal code for sparse symmetric systems. Tech. Rep. RAL-TR-2011-024, Rutherford Appleton Laboratory (2011)
Manteuffel, T.A.: The Tchebychev iteration for nonsymmetric linear systems. Numer. Math. 28, 307–327 (1977)
Manteuffel, T.A.: Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration. Numer. Math. 31, 183–208 (1978)
Rutishauser, H.: Theory of gradient methodsIn: Refined iterative methods for computation of the solution and the Eigenvalues of self-adjoint boundary value problems, Nr. 8, pp. 24–49. Birkhauser, Basel (1959)
Saad, Y.: A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Stat. Comput. 14(2), 461–469 (1993)
Skeel, R.D.: Iterative refinement implies numerical stability for Gaussian elimination. Math. Comput. 35, 817–832 (1980)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work was supported by the EPSRC Grant EP/E053351/1
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
About this article
Cite this article
Arioli, M., Scott, J. Chebyshev acceleration of iterative refinement. Numer Algor 66, 591–608 (2014). https://doi.org/10.1007/s11075-013-9750-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-013-9750-7