Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
<|reference_start|>Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices: Let $\orig{A}$ be any matrix and let $A$ be a slight random perturbation of $\orig{A}$. We prove that it is unlikely that $A$ has large condition number. Using this result, we prove it is unlikely that $A$ has large growth factor under Gaussian elimination without pivoting. By combining these results, we bound the smoothed precision needed by Gaussian elimination without pivoting. Our results improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan (SIAM J. Matrix Anal. Appl., 1997).<|reference_end|>
@article{sankar2003smoothed,
    title={Smoothed Analysis of the Condition Numbers and Growth Factors of
  Matrices},
    author={Arvind Sankar, Daniel A. Spielman, Shang-Hua Teng},
    journal={arXiv preprint arXiv:cs/0310022},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0310022},
    primaryClass={cs.NA cs.DS}
}