Smoothed Analysis for the Conjugate Gradient Algorithm
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Smoothed Analysis for the Conjugate Gradient Algorithm
|
|
| Creator |
Menon, G.
Trogdon, T. |
|
| Description |
The purpose of this paper is to establish bounds on the rate of convergence of the conjugate gradient algorithm when the underlying matrix is a random positive definite perturbation of a deterministic positive definite matrix. We estimate all finite moments of a natural halting time when the random perturbation is drawn from the Laguerre unitary ensemble in a critical scaling regime explored in Deift et al. (2016). These estimates are used to analyze the expected iteration count in the framework of smoothed analysis, introduced by Spielman and Teng (2001). The rigorous results are compared with numerical calculations in several cases of interest.
|
|
| Date |
2019-02-18T14:45:41Z
2019-02-18T14:45:41Z 2016 |
|
| Type |
Article
|
|
| Identifier |
Smoothed Analysis for the Conjugate Gradient Algorithm / G. Menon, T. Trogdon // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 22 назв. — англ.
1815-0659 2010 Mathematics Subject Classification: 60B20; 65C50; 35Q15 DOI:10.3842/SIGMA.2016.109 http://dspace.nbuv.gov.ua/handle/123456789/148528 |
|
| Language |
en
|
|
| Relation |
Symmetry, Integrability and Geometry: Methods and Applications
|
|
| Publisher |
Інститут математики НАН України
|
|