Krylov-aware stochastic trace estimation

Abstract

We introduce an algorithm for estimating the trace of a matrix function $f(\mathbf{A})$ using implicit products with a symmetric matrix $\mathbf{A}$. Existing methods for implicit trace estimation of a matrix function tend to treat matrix-vector products with $f(\mathbf{A})$ as a black-box to be computed by a Krylov subspace method. Like other recent algorithms for implicit trace estimation, our approach is based on a combination of deflation and stochastic trace estimation. However, we take a closer look at how products with $f(\mathbf{A})$ are integrated into these approaches which enables several efficiencies not present in previously studied methods. In particular, we describe a Krylov subspace method for computing a low-rank approximation of a matrix function by a computationally efficient projection onto Krylov subspace.

arXiv commentFigure 5.1 differs somewhat from the published version due to a clerical error made when uploading the images to the journal

References in corpus (9)

• The Kernel Polynomial Method
• The foundations of statistical mechanics from entanglement: Individual states vs. averages
• Accuracy of the finite-temperature Lanczos method compared to simple typicality-based estimates
• Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
• Finite-temperature properties of the Kitaev-Heisenberg models on kagome and triangular lattices studied by improved finite-temperature Lanczos methods
• Estimating the Trace of the Matrix Inverse by Interpolating from the Diagonal of an Approximate Inverse
• 2-norm error bounds and estimates for Lanczos approximations to linear systems and rational matrix functions
• Assessing stochastic algorithms for large scale nonlinear least squares problems using extremal probabilities of linear combinations of gamma random variables
• Error bounds for Lanczos-based matrix function approximation

Cited by in corpus (3)

• Numerical computation of the equilibrium-reduced density matrix for strongly coupled open quantum systems
• A posteriori error bounds for the block-Lanczos method for matrix function approximation
• Faster randomized partial trace estimation