Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.02023 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910049882865664 |
|---|---|
| author | Detherage, Isabel Shah, Rikhav |
| author_facet | Detherage, Isabel Shah, Rikhav |
| contents | This paper highlights a formal connection between two families of widely used matrix factorization algorithms in numerical linear algebra. One family consists of the Jacobi eigenvalue algorithm and its variants for computing the Hermitian eigendecomposition and singular value decomposition. The other consists of Gaussian elimination and the Gram-Schmidt procedure with various pivoting rules for computing the Cholesky decomposition and QR decomposition respectively.
Both families are cast as special cases of a more general class of factorization algorithms. We provide a randomized pivoting rule that applies to this general class (which differs substantially from the usual pivoting rules for Gaussian elimination / Gram-Schmidt) which admits a unified analysis of the entire class of algorithms. The result is the same linear rate of convergence for each algorithm, irrespective of which factorization it computes.
One important consequence of this randomized pivoting rule is a provable polynomial bound on the numerical stability of the Jacobi eigenvalue algorithm without any preconditioning, which addresses a longstanding open problem of Demmel and Veselić `92. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02023 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Matrix Factorizations with Uniformly Random Pivoting Detherage, Isabel Shah, Rikhav Numerical Analysis 65F15, 65F25 G.1.3 This paper highlights a formal connection between two families of widely used matrix factorization algorithms in numerical linear algebra. One family consists of the Jacobi eigenvalue algorithm and its variants for computing the Hermitian eigendecomposition and singular value decomposition. The other consists of Gaussian elimination and the Gram-Schmidt procedure with various pivoting rules for computing the Cholesky decomposition and QR decomposition respectively. Both families are cast as special cases of a more general class of factorization algorithms. We provide a randomized pivoting rule that applies to this general class (which differs substantially from the usual pivoting rules for Gaussian elimination / Gram-Schmidt) which admits a unified analysis of the entire class of algorithms. The result is the same linear rate of convergence for each algorithm, irrespective of which factorization it computes. One important consequence of this randomized pivoting rule is a provable polynomial bound on the numerical stability of the Jacobi eigenvalue algorithm without any preconditioning, which addresses a longstanding open problem of Demmel and Veselić `92. |
| title | Matrix Factorizations with Uniformly Random Pivoting |
| topic | Numerical Analysis 65F15, 65F25 G.1.3 |
| url | https://arxiv.org/abs/2505.02023 |