Impact of matrix topological properties on the convergence of the conjugate gradient method
Abstract
It is well known that the matrix structure affects the convergence of iterative methods, particularly those utilizing Krylov subspaces. The matrix structure, determined by its graph, dictates the propagation order of updates to the vector components that are recursively computed during the conjugate gradient method iterations. Along with the propagation of these component updates, round-off errors also propagate. We present a model for the propagation and accumulation of round-off errors and demonstrate that the larger the values of topological characteristics of the matrix graph, such as its diameter, effective diameter, and pseudodiameter, the slower the round-off error accumulates during the method's iterations, and the longer the propagation of round-off errors remains local when computing the components of the search direction, residual, and approximate solution vectors. Round-off errors arising during the computation of these components affect only those components whose corresponding vertices in the matrix graph are at a distance not exceeding the current iteration number. As the iteration number increases, the propagation of round-off errors between the vertices of the matrix graph becomes global, leading to the loss of orthogonality of residuals and conjugacy of search directions. In the context of mixed-precision computations, this implies that for a matrix with a larger graph diameter (or, more practically, effective diameter), a greater number of method iterations can be performed in a lower-precision mode before the onset of convergence stagnation.
Related
- Preconditioned Three-Term Conjugate Gradient Framework for Nonconvex Finite Minimax Problems
- Deflation-Based Spectral Preconditioning for the Conjugate Gradient Method on Perturbed Systems
- Quantum-compatible Riemannian conjugate gradient for ground-state preparation
- A Conjugate Gradient Formulation of the EnKF Algorithm
- A family of spectral conjugate gradient algorithms derived by least-squares approximations based on a modified quasi--Newton update with application to a revised robust binary classification model
BibTeX
@misc{prolubnikov2026impact,
title = {{Impact of matrix topological properties on the convergence of the conjugate gradient method}},
author = {Alexander Prolubnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15393},
eprint = {2610.15393},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15393},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Impact of matrix topological properties on the convergence of the conjugate gradient method
AU - Alexander Prolubnikov
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15393
UR - https://arxiv.org/abs/2610.15393
AB - It is well known that the matrix structure affects the convergence of iterative methods, particularly those utilizing Krylov subspaces. The matrix structure, determined by its graph, dictates the propagation order of updates to the vector components that are recursively computed during the conjugate gradient method iterations. Along with the propagation of these component updates, round-off errors also propagate. We present a model for the propagation and accumulation of round-off errors and demonstrate that the larger the values of topological characteristics of the matrix graph, such as its diameter, effective diameter, and pseudodiameter, the slower the round-off error accumulates during the method's iterations, and the longer the propagation of round-off errors remains local when computing the components of the search direction, residual, and approximate solution vectors. Round-off errors arising during the computation of these components affect only those components whose corresponding vertices in the matrix graph are at a distance not exceeding the current iteration number. As the iteration number increases, the propagation of round-off errors between the vertices of the matrix graph becomes global, leading to the loss of orthogonality of residuals and conjugacy of search directions. In the context of mixed-precision computations, this implies that for a matrix with a larger graph diameter (or, more practically, effective diameter), a greater number of method iterations can be performed in a lower-precision mode before the onset of convergence stagnation.
ER -