{"id":794,"date":"2017-12-02T11:26:30","date_gmt":"2017-12-02T11:26:30","guid":{"rendered":"http:\/\/www.mub.eps.manchester.ac.uk\/in-abstract\/?p=794"},"modified":"2017-12-07T08:53:17","modified_gmt":"2017-12-07T08:53:17","slug":"how-to-solve-sensitive-equations-accurately","status":"publish","type":"post","link":"https:\/\/www.mub.eps.manchester.ac.uk\/in-abstract\/how-to-solve-sensitive-equations-accurately\/","title":{"rendered":"A New Analysis of Iterative Refinement and its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems"},"content":{"rendered":"

How to Solve Sensitive Equations Accurately<\/strong><\/p>\n

Some systems of linear equations are ill conditioned: a tiny change in the coefficients can produce a large change in the solution. There is growing interest in using lower precisions such as single or even half precision in climate and weather modeling and machine learning, but this brings an increased likelihood that the linear equations encountered will be very ill conditioned relative to the working precision. Solving such systems accurately in the finite precision arithmetic available on computers is problematic. Researchers at the University of Manchester and the Courant Institute of Mathematical Sciences have found a way to obtain high accuracy without greatly increasing the cost of the standard LU factorization-based solution process. They employ iterative refinement (IR), a long-standing technique for improving the accuracy of a computed solution to a nonsingular linear system $Ax = b$. It makes use of residuals computed in extra precision, typically at twice the working precision, and existing results guarantee convergence if the matrix $A$ is not too ill conditioned. This work identifies a mechanism that allows iterative refinement to produce solutions to full machine accuracy even for systems with a numerical singular matrix $A$. Building on a detailed rounding error analysis, an iterative refinement method has been developed that solves the update equations using the GMRES iterative method. The key innovation is to use the computed LU factors as preconditioners, exploiting the information in the factors to greatly reduce the condition number of $A$. In numerical experiments GMRES-IR yields fully accurate solutions in at most $3$ steps in every case.<\/p>\n

<\/p>\n