Smoothed analysis for the conjugate gradient algorithm

DOI10.3842/SIGMA.2016.109zbMath1375.60022arXiv1605.06438OpenAlexW2401489411MaRDI QIDQ2520124

Thomas Trogdon, Govind K. Menon

Publication date: 13 December 2016

Published in: SIGMA. Symmetry, Integrability and Geometry: Methods and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.06438

zbMATH Keywords

conjugate gradient algorithmLaguerre unitary ensembleWishart ensemblesmoothed analysis

Mathematics Subject Classification ID

Related Items (4)

Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices ⋮ Universality for Eigenvalue Algorithms on Sample Covariance Matrices ⋮ Halting time is predictable for large models: a universality property and average-case analysis ⋮ The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic

Uses Software

• numericaluniversality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the condition number of the critically-scaled Laguerre unitary ensemble
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• Level-spacing distributions and the Airy kernel
• The spectrum edge of random matrix ensembles.
• Universality in numerical computations with random data
• How long does it take to compute the eigenvalues of a random symmetric matrix?
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Smoothed analysis of algorithms
• Eigenvalues and Condition Numbers of Random Matrices
• Error Analysis of Direct Methods of Matrix Inversion
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Universality for the Toda Algorithm to Compute the Largest Eigenvalue of a Random Matrix
• Universal halting times in optimization and machine learning
• Smoothed analysis of algorithms
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Methods of conjugate gradients for solving linear systems

This page was built for publication: Smoothed analysis for the conjugate gradient algorithm