Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
Authors:
- Arvind SankarASArvind Sankar
- Daniel A. SpielmanDSDaniel A. Spielman
- Shang-Hua TengSTShang-Hua Teng
Top Cited Papers
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 28 (2) , 446-476
Abstract
Let Å be an arbitrary matrix and let A be a slight random perturbation of Å. We prove that it is unlikely that A has a large condition number. Using this result, we prove that it is unlikely that A has large growth factor under Gaussian elimination without pivoting. By combining these results, we show that the smoothed precision necessary to solve Ax = b, for any b, using Gaussian elimination without pivoting is logarithmic. Moreover, when Å is an all-zero square matrix, our results significantly improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan (SIAM J. Matrix Anal. Appl., 18 (1997), pp. 499-517).Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Smoothed analysis of algorithmsJournal of the ACM, 2004
- Smoothed analysis of termination of linear programming algorithmsMathematical Programming, 2003
- The Expected Norm of Random MatricesCombinatorics, Probability and Computing, 2000
- Discrete Approximations to Continuous Univariate Distributions—an Alternative to SimulationJournal of the Royal Statistical Society Series B: Statistical Methodology, 1999
- Applied Numerical Linear Algebra1997
- Incorporating Condition Measures into the Complexity Theory of Linear ProgrammingSIAM Journal on Optimization, 1995
- Probability in Banach Spaces, 91994
- Geometric Algorithms and Combinatorial Optimization1993
- Eigenvalues and Condition Numbers of Random MatricesSIAM Journal on Matrix Analysis and Applications, 1988
- The probability that a numerical analysis problem is difficultMathematics of Computation, 1988