Forward and backward error bounds for a mixed precision preconditioned conjugate gradient algorithm

Abstract

The preconditioned conjugate gradient (PCG) algorithm is one of the most popular algorithms for solving large-scale linear systems $Ax=b$, where $A$ is a symmetric positive definite matrix. Rather than computing residuals directly, it updates the residual vectors recursively. Current analyses of the conjugate gradient (CG) algorithm in finite precision typically assume that the norm of the recursively updated residual goes orders of magnitude below the machine precision, focusing mainly on bounding the residual gap thereafter. This work introduces a framework for the PCG algorithm and provides rigorous proofs that the relative backward and forward errors of the computed results of PCG can reach the levels $O(u)$ and $O(u)\hat{I}º(A{)}^{1/2}$, respectively, after a sufficient number of iterations without relying on an assumption concerning the norm of the recursively updated residual, where $u$ represents the unit roundoff and $\hat{I}º(A)$ is the condition number of $A$. Our PCG framework further shows that applying preconditioners in low precision does not compromise the accuracy of the final results, provided that reasonable conditions are satisfied. Moreover, this framework introduces a new split PCG variant that improves upon the classical split PCG algorithm when the left preconditioner is applied in low precision. Our theoretical results are illustrated through a set of numerical experiments.

39 pages, 5 figures