Abstract: The Bayesian Conjugate Gradient method (BayesCG) is a probabilistic generalization of the Conjugate Gradient method (CG) for solving linear systems with real symmetric positive definite coefficient matrices. Our CG-based implementation of BayesCG under a structure-exploiting prior distribution represents an 'uncertainty-aware' version of CG. Its output consists of CG iterates and posterior covariances that can be propagated to subsequent computations. The covariances have low-rank and are maintained in factored form. This allows easy generation of accurate samples to probe uncertainty in downstream computations. Numerical experiments confirm the effectiveness of the low-rank posterior covariances.
Introduction
When solving large linear systems ($\mathbf{Ax} = \mathbf{b}$), the Conjugate Gradient (CG) method is a cornerstone of computational science. However, in practice, CG is almost always terminated early to save time, introducing epistemic uncertainty about the true solution. Traditional numerical error estimates typically provide only a single scalar value, such as a residual norm. This is often inadequate when the CG output serves as an input for a larger computational pipeline, as downstream algorithms cannot easily ingest a static error bound to understand how that error propagates.
Probabilistic numerics addresses this by treating the unknown exact solution as a probability distribution. This paper introduces an "uncertainty-aware" version of CG called BayesCG, which models the error introduced by early termination. By utilizing a novel, structure-exploiting "Krylov prior," the method outputs both the standard CG solution and a low-rank posterior covariance matrix, allowing researchers to sample and propagate solver uncertainty with minimal computational overhead.
Methodology
The authors revamp the BayesCG framework through several key theoretical and practical innovations:
- Singular Priors: The framework is extended to handle singular prior covariances, allowing the algorithm to restrict its "beliefs" perfectly to the Krylov subspace. This aligns the probabilistic model with the deterministic reality of standard CG.
- The Krylov Prior: A new prior is introduced, built directly from the Krylov subspace generated by the CG algorithm itself.
- Error Matching: A specific scaling (diagonal matrix $\Phi$) is designed for the Krylov prior so that the posterior mean equals the standard CG iterate, and the covariance trace matches the true CG error (specifically, the $\mathbf{A}$-norm error).
- Low-Rank Approximation: To ensure practicality, an efficient algorithm runs standard CG for $m$ steps followed by $d$ additional "delay" iterations. These extra steps compute the factors of a rank-$d$ approximate posterior covariance matrix.
Experimental Evaluation
The method was evaluated on both small dense matrices ($n=100$) designed to test finite-precision behavior and large sparse matrices ($n=11,948$) from structural engineering datasets (BCSSTK18).
Key Insights
- Free Covariance Factorization: Under the Krylov prior, the posterior covariance can be maintained in a factored form ($\mathbf{F}\mathbf{F}^T$) without extra arithmetic operations. This ensures efficiency and numerical stability, preventing the matrix from becoming indefinite due to rounding errors.
- Bridging Statistics and Linear Algebra: The authors prove a direct link between the probabilistic uncertainty model and classical numerical error bounds: the trace of the specific posterior covariance exactly equals the standard $\mathbf{A}$-norm error of CG.
Key Results
- Accurate Uncertainty Tracking: The new BayesCG implementation produces posterior samples that tightly track the true approximation error. This is a significant improvement over previous versions using an "inverse prior," which often diverged or required expensive reorthogonalization.
- Scalability and Efficiency: For large sparse systems, a rank-50 approximation (using only 50 extra "delay" iterations) produced highly reliable uncertainty estimates over thousands of iterations. The factored form of the covariance makes generating samples for downstream tasks virtually free in terms of computational cost.
Conclusion and Future Work
While the current method excels at generating samples, analytically propagating the resulting posterior distribution through subsequent equations remains a challenge, currently requiring empirical sampling (Monte Carlo). Future work will focus on a rigorous statistical proof of calibration under the Krylov prior and testing the method in real-world pipelines, such as randomized algorithms for generalized singular value decomposition and hyper-differential sensitivity analysis.
Summary updated