Runtime complexity estimation for accurate solution of linear systems

An established idea for the accurate solution of linear systems is to use iterative refinement. More recently it has been shown that a modification of iterative refinement can be advantageous for high precision computation. In this work we describe a simplified complexity analysis that reliably shows when an iterative solution procedure is advantageous over a direct solution method. The analysis involves an estimate of the condition number of a matrix and is efficient enough to be used for automatic method selection at runtime in a linear solver. We also introduce a scaling technique that is advantageous when solving for the solution and correction steps using machine precision. Numerical experiments, using an implementation developed in the Mathematica kernel, are provided to confirm the theory that has been presented.