RELIABLE UPDATED RESIDUALS IN HYBRID BI-CG METHODS

Many iterative methods for solving linear equations Ax=b aim for accur ate approximations to x, and they do so by updating residuals iterativ ely. In finite precision arithmetic, these computed residuals may be i naccurate, that is, they may differ significantly from the (true) resi duals that correspond to the computed approximations. In this paper we will propose variants on Neumaier's strategy, originally proposed for CGS, and explain its success. In particular, we will propose a more r estrictive strategy for accumulating groups of updates for updating th e residual and the approximation, and we will show that this may impro ve the accuracy significantly, while maintaining speed of convergence. This approach avoids restarts and allows for more reliable stopping c riteria. We will discuss updating conditions and strategies that are e fficient, lead to accurate residuals, and are easy to implement. For C GS and Bi-CG these strategies are particularly attractive, but they ma y also be used to improve Bi-CGSTAB, BiCGstab(l), as well as other met hods.