## Abstract

Iterative renement is a long-standing technique for improving the accuracy of a

computed solution to a nonsingular linear system Ax = b obtained via LU factorization. It makes use of residuals computed in extra precision, typically at twice the working precision, and existing results guarantee convergence if the matrix A has condition number safely less than the reciprocal of the unit roundo, u. We identify a mechanism that allows iterative renement to produce solutions

with normwise relative error of order u to systems with condition numbers of order u􀀀1 or larger, provided that the update equation is solved with a relative error suciently less than 1. A new rounding error analysis is given and its implications are analyzed. Building on the analysis, we develop a GMRES-based iterative renement method (GMRES-IR) that makes use of the computed LU factors as preconditioners. GMRES-IR exploits the fact that even if A is extremely ill conditioned the LU factors contain enough information that preconditioning can greatly reduce the condition number of A. Our rounding error analysis and numerical experiments show that GMRES-IR can succeed where standard renement fails, and that it can provide accurate solutions to systems with

condition numbers of order u􀀀1 and greater. Indeed in our experiments with such matrices|both random and from the University of Florida Sparse Matrix Collection|GMRES-IR yields a normwise relative error of order u in at most 3 steps in every case.

computed solution to a nonsingular linear system Ax = b obtained via LU factorization. It makes use of residuals computed in extra precision, typically at twice the working precision, and existing results guarantee convergence if the matrix A has condition number safely less than the reciprocal of the unit roundo, u. We identify a mechanism that allows iterative renement to produce solutions

with normwise relative error of order u to systems with condition numbers of order u􀀀1 or larger, provided that the update equation is solved with a relative error suciently less than 1. A new rounding error analysis is given and its implications are analyzed. Building on the analysis, we develop a GMRES-based iterative renement method (GMRES-IR) that makes use of the computed LU factors as preconditioners. GMRES-IR exploits the fact that even if A is extremely ill conditioned the LU factors contain enough information that preconditioning can greatly reduce the condition number of A. Our rounding error analysis and numerical experiments show that GMRES-IR can succeed where standard renement fails, and that it can provide accurate solutions to systems with

condition numbers of order u􀀀1 and greater. Indeed in our experiments with such matrices|both random and from the University of Florida Sparse Matrix Collection|GMRES-IR yields a normwise relative error of order u in at most 3 steps in every case.

Original language | English |
---|---|

Pages (from-to) | A2834 |

Journal | SIAM Journal on Scientific Computing |

Volume | 39 |

Issue number | 6 |

DOIs | |

Publication status | Published - 6 Dec 2017 |

## Keywords

- ill-conditioned linear system
- Iterative refinement
- multiple precision
- Mixed precision
- Rounding error analysis
- Backward error
- Forward error
- GMRES
- Preconditioning