Journal
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
Volume 28, Issue 2, Pages 446-476Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0895479803436202
Keywords
smoothed analysis; condition number; Gaussian elimination; growth factor
Categories
Ask authors/readers for more resources
Let (A) over bar be an arbitrary matrix and let A be a slight random perturbation of (A) over bar. 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 (A) over bar 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).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available