Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2003
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908599809212416 |
|---|---|
| author | Sankar, Arvind Spielman, Daniel A. Teng, Shang-Hua |
| author_facet | Sankar, Arvind Spielman, Daniel A. Teng, Shang-Hua |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0310022 |
| institution | arXiv |
| publishDate | 2003 |
| record_format | arxiv |
| spellingShingle | Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices Sankar, Arvind Spielman, Daniel A. Teng, Shang-Hua Numerical Analysis Data Structures and Algorithms G.1.3 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). |
| title | Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices |
| topic | Numerical Analysis Data Structures and Algorithms G.1.3 |
| url | https://arxiv.org/abs/cs/0310022 |