1. Fast Approximate Determinants Using Rational Functions
- Author
-
Colthurst, Thomas, Vasudevan, Srinivas, Lottes, James, and Patton, Brian
- Subjects
Computer Science - Data Structures and Algorithms ,Mathematics - Numerical Analysis ,G.1.3 - Abstract
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\'ern-$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., Comment: 22 pages, 17 figures
- Published
- 2024