Fast Approximate Determinants Using Rational Functions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910436288364544 |
|---|---|
| author | Colthurst, Thomas Vasudevan, Srinivas Lottes, James Patton, Brian |
| author_facet | Colthurst, Thomas Vasudevan, Srinivas Lottes, James Patton, Brian |
| contents | We show how rational function approximations to the logarithm, such as $\log z \approx (z^2 - 1)/(z^2 + 6z + 1)$, can be turned into fast algorithms for approximating the determinant of a very large matrix. We empirically demonstrate that when combined with a good preconditioner, the third order rational function approximation offers a very good trade-off between speed and accuracy when measured on matrices coming from Matérn-$5/2$ and radial basis function Gaussian process kernels. In particular, it is significantly more accurate on those matrices than the state-of-the-art stochastic Lanczos quadrature method for approximating determinants while running at about the same speed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03474 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Approximate Determinants Using Rational Functions Colthurst, Thomas Vasudevan, Srinivas Lottes, James Patton, Brian Data Structures and Algorithms Numerical Analysis G.1.3 We show how rational function approximations to the logarithm, such as $\log z \approx (z^2 - 1)/(z^2 + 6z + 1)$, can be turned into fast algorithms for approximating the determinant of a very large matrix. We empirically demonstrate that when combined with a good preconditioner, the third order rational function approximation offers a very good trade-off between speed and accuracy when measured on matrices coming from Matérn-$5/2$ and radial basis function Gaussian process kernels. In particular, it is significantly more accurate on those matrices than the state-of-the-art stochastic Lanczos quadrature method for approximating determinants while running at about the same speed. |
| title | Fast Approximate Determinants Using Rational Functions |
| topic | Data Structures and Algorithms Numerical Analysis G.1.3 |
| url | https://arxiv.org/abs/2405.03474 |