×
Menon, Govind; Trogdon, Thomas

Smoothed analysis for the conjugate gradient algorithm. (English) Zbl 1375.60022

SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 109, 22 p. (2016).
Summary: 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 [the first author et al., Discrete Contin. Dyn. Syst. 36, No. 8, 4287–4347 (2016; Zbl 1335.60008)]. These estimates are used to analyze the expected iteration count in the framework of smoothed analysis, introduced by D. Spielman and S.-H. Teng [in: Proceedings of the 33rd annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press. 296–305 (2001; Zbl 1323.68636)]. The rigorous results are compared with numerical calculations in several cases of interest.

Cited in 4 Documents

MSC:

60B20 Random matrices (probabilistic aspects)
65C50 Other computational problems in probability (MSC2010)
35Q15 Riemann-Hilbert problems in context of PDEs
65F10 Iterative numerical methods for linear systems

Keywords:

conjugate gradient algorithm; Wishart ensemble; Laguerre unitary ensemble; smoothed analysis

Citations:

Zbl 1335.60008; Zbl 1323.68636

Software:

numericaluniversality
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Deift, Percy A., Orthogonal polynomials and random matrices: a {R}iemann–{H}ilbert approach, Courant Lecture Notes in Mathematics, 3, viii+273, (1999), New York University, Courant Institute of Mathematical Sciences, New York, Amer. Math. Soc., Providence, RI · doi:10.1090/cln/003
[2] Deift, Percy A. and Trogdon, Thomas, Universality for the {T}oda algorithm to compute the eigenvalues of a random matrix, (None) · Zbl 1454.60012
[3] Deift, Percy A. and Menon, Govind and Olver, Sheehan and Trogdon, Thomas, Universality in numerical computations with random data, Proceedings of the National Academy of Sciences of the United States of America, 111, 42, 14973-14978, (2014) · Zbl 1355.65019 · doi:10.1073/pnas.1413446111
[4] Deift, Percy A. and Trogdon, Thomas and Menon, Govind, On the condition number of the critically-scaled {L}aguerre unitary ensemble, Discrete and Continuous Dynamical Systems. Series A, 36, 8, 4287-4347, (2016) · Zbl 1335.60008 · doi:10.3934/dcds.2016.36.4287
[5] Edelman, Alan, Eigenvalues and condition numbers of random matrices, SIAM Journal on Matrix Analysis and Applications, 9, 4, 543-560, (1988) · Zbl 0678.15019 · doi:10.1137/0609045
[6] Forrester, P. J., The spectrum edge of random matrix ensembles, Nuclear Physics. B, 402, 3, 709-728, (1993) · Zbl 1043.82538 · doi:10.1016/0550-3213(93)90126-A
[7] Golub, Gene H. and Van Loan, Charles F., Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, xiv+756, (2013), Johns Hopkins University Press, Baltimore, MD · Zbl 1268.65037
[8] Greenbaum, A., Behavior of slightly perturbed {L}anczos and conjugate-gradient recurrences, Linear Algebra and its Applications, 113, 7-63, (1989) · Zbl 0662.65032 · doi:10.1016/0024-3795(89)90285-1
[9] Greenbaum, A. and Strako{\v{s}}, Z., Predicting the behavior of finite precision {L}anczos and conjugate gradient computations, SIAM Journal on Matrix Analysis and Applications, 13, 1, 121-137, (1992) · Zbl 0755.65037 · doi:10.1137/0613011
[10] Hestenes, Magnus R. and Stiefel, Eduard, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49, 409-436, (1952) · Zbl 0048.09901
[11] Liesen, J{\"o}rg and Strako{\v{s}}, Zden{\v{e}}k, Krylov subspace methods. Principles and analysis, Numerical Mathematics and Scientific Computation, xvi+391, (2013), Oxford University Press, Oxford · Zbl 1263.65034
[12] Marchenko, V. A. and Pastur, L. A., Distribution of eigenvalues for some sets of random matrices, Mathematics of the USSR-Sbornik, 1, 4, 457-483, (1967) · Zbl 0162.22501 · doi:10.1070/SM1967v001n04ABEH001994
[13] N{IST} handbook of mathematical functions, xvi+951, (2010), U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC, Cambridge University Press, Cambridge · Zbl 1198.00002
[14] Pfrang, Christian W. and Deift, Percy and Menon, Govind, How long does it take to compute the eigenvalues of a random symmetric matrix?, Random Matrix Theory, Interacting Particle Systems, and Integrable Systems, Math. Sci. Res. Inst. Publ., 65, 411-442, (2014), Cambridge University Press, New York · Zbl 1326.65050
[15] Sagun, Levent and Trogdon, Thomas and LeCun, Yann, Universality in halting time and its applications in optimization, (None) · Zbl 1425.68114
[16] Sankar, Arvind and Spielman, Daniel A. and Teng, Shang-Hua, Smoothed analysis of the condition numbers and growth factors of matrices, SIAM Journal on Matrix Analysis and Applications, 28, 2, 446-476, (2006) · Zbl 1179.65033 · doi:10.1137/S0895479803436202
[17] Simon, Barry, Trace ideals and their applications, Mathematical Surveys and Monographs, 120, viii+150, (2005), Amer. Math. Soc., Providence, RI · Zbl 1074.47001
[18] Spielman, Daniel and Teng, Shang-Hua, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, Proceedings of the {T}hirty-{T}hird {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing, 296-305, (2001), ACM, New York · Zbl 1323.68636 · doi:10.1145/380752.380813
[19] Spielman, Daniel A. and Teng, Shang-Hua, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, Journal of the ACM, 51, 3, 385-463, (2004) · Zbl 1192.90120 · doi:10.1145/990308.990310
[20] Szeg{\H{o}}, G{\'a}bor, Orthogonal polynomials, American Mathematical Society, Colloquium Publications, 23, xiii+432, (1975), Amer. Math. Soc., Providence, RI · Zbl 0305.42011
[21] Tracy, Craig A. and Widom, Harold, Level-spacing distributions and the {A}iry kernel, Communications in Mathematical Physics, 159, 1, 151-174, (1994) · Zbl 0789.35152 · doi:10.1007/BF02100489
[22] Wilkinson, J. H., Error analysis of direct methods of matrix inversion, Journal of the ACM, 8, 281-330, (1961) · Zbl 0109.09005 · doi:10.1145/321075.321076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.