Наукова електронна бібліотека
періодичних видань НАН України
періодичних видань НАН України
Smoothed Analysis for the Conjugate Gradient Algorithm
Репозиторій DSpace/Manakin
- Домашня сторінка
- →
- Фізико-технічні та математичні науки
- →
- Відділення математики
- →
- Symmetry, Integrability and Geometry: Methods and Applications (SIGMA)
- →
- Symmetry, Integrability and Geometry: Methods and Applications, 2016, том 12
- →
- Symmetry, Integrability and Geometry: Methods and Applications, 2016, том 12, випуск за цей рік
- →
- Переглянути статтю
JavaScript is disabled for your browser. Some features of this site may not work without it.
Smoothed Analysis for the Conjugate Gradient Algorithm
Інший ID:
2010 Mathematics Subject Classification: 60B20; 65C50; 35Q15
DOI:10.3842/SIGMA.2016.109
DOI:10.3842/SIGMA.2016.109
Посилання:
Smoothed Analysis for the Conjugate Gradient Algorithm / G. Menon, T. Trogdon // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 22 назв. — англ.
Підтримка:
This paper is a contribution to the Special Issue on Asymptotics and Universality in Random Matrices,
Random Growth Processes, Integrable Systems and Statistical Physics in honor of Percy Deift and Craig Tracy.
The full collection is available at http://www.emis.de/journals/SIGMA/Deift-Tracy.html.
This work was supported in part by grants NSF-DMS-1411278 (GM) and NSF-DMS-1303018
(TT). The authors thank Anne Greenbaum and Zdenˇek Strakoˇs for useful conversations, Folkmar
Bornemann for suggesting that we consider the framework of smoothed analysis and the
anonymous referees for suggesting additional numerical experiments.
Дата:
2016
Переглядів:
479
Завантажень:
257
Анотація:
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.
