Conjugate Gradient Methods are Not Efficient: Experimental Study of the Locality Limitation
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908768776749056 |
|---|---|
| author | Rüde, Ulrich |
| author_facet | Rüde, Ulrich |
| contents | The convergence of the Conjugate Gradient method is subject to a locality limitation which imposes a lower bound on the number of iterations required before a qualitatively accurate approximation can be obtained. This limitation originates from the restricted transport of information in the graph induced by the sparsity pattern of the system matrix. In each iteration, information from the right-hand side can propagate only across directly connected graph nodes. The diameter of this graph therefore determines a minimum number of iterations that is necessary to achieve an acceptable level of accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_10322 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Conjugate Gradient Methods are Not Efficient: Experimental Study of the Locality Limitation Rüde, Ulrich Numerical Analysis 65F10, 65F50, 65N22 G.1.3; G.1.7; G.1.8 The convergence of the Conjugate Gradient method is subject to a locality limitation which imposes a lower bound on the number of iterations required before a qualitatively accurate approximation can be obtained. This limitation originates from the restricted transport of information in the graph induced by the sparsity pattern of the system matrix. In each iteration, information from the right-hand side can propagate only across directly connected graph nodes. The diameter of this graph therefore determines a minimum number of iterations that is necessary to achieve an acceptable level of accuracy. |
| title | Conjugate Gradient Methods are Not Efficient: Experimental Study of the Locality Limitation |
| topic | Numerical Analysis 65F10, 65F50, 65N22 G.1.3; G.1.7; G.1.8 |
| url | https://arxiv.org/abs/2601.10322 |