Impact of metric characteristics of the matrix graph on the convergence of the conjugate gradient method
math.NA, cs.NA
Submitted: 2026-10-11
Updated: 2026-11-05
License: http://creativecommons.org/licenses/by/4.0/
The gist: A model of propagation and accumulation of errors caused by round-off errors during conjugate gradient (CG) iterations is proposed…
Terminology
Abstract
A model of propagation and accumulation of errors caused by round-off errors during conjugate gradient (CG) iterations is proposed, based on their interpretation as iterations of traversals of the linear system matrix graph. In the matrix graph, vertices correspond to the components of the search direction, residual, and approximate solution vectors, which are computed recursively at CG iterations. It is shown that when the number of CG iterations performed is less than the distance between two vertices in the graph, the round-off errors arising in the computation of one component do not affect the errors in the computation of another and are not correlated. At early iterations, errors propagate locally between neighboring vertices and are locally correlated. As the errors become sufficiently global, loss of orthogonality of residuals and conjugacy of search directions occurs, and stagnation of the iterative process sets in. The results of computational experiments are presented for matrices corresponding to graphs with a prescribed diameter, for Laplacians of differential equations, and for random matrices. These results demonstrate that the diameter and its approximate values, in particular the pseudodiameter, due to their low computational cost for sparse graphs, can be used in mixed-precision algorithms for solving linear systems, namely, for switching precision modes as round-off errors propagate and accumulate.
Sources
- Towards understanding CG and GMRES through examples
- Conjugate Gradient Methods are Not Efficient: Experimental Study of the Locality Limitation
- PROPAGATE: a seed propagation framework to compute Distance-based metrics on Very Large Graphs
- Parameter optimization for restarted mixed precision iterative sparse solver
Related papers
- Do physics-informed neural networks (PINNs) need to be deep? Shallow PINNs using the Levenberg-Marquardt algorithm
- A Neural-preconditioned Poisson Solver for Mixed Dirichlet and Neumann Boundary Conditions
- Advanced Linear Algebra with Applications - Part I (Numerical linear algebra for PDEs, machine learning, and data assimilation)
- Operator learning meets inverse problems: A probabilistic perspective
- Second-order consistency for learning chaotic dynamics via randomized Jacobian matching
- Windowed thinning and query complexity for the bouncy particle and Zigzag samplers