A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
Andreas Frommer, M. N. Khalil, Gustavo Ramirez‐Hidalgo · SIAM Journal on Scientific Computing · 2022
The trace of a matrix function $f(A)$, most notably of the matrix inverse, can be estimated stochastically using samples $x^*f(A)x$ if the components of the random vectors $x$ obey an appropriate probability distribution. However such a Monte Carlo sampling suffers from the fact that the accuracy depends quadratically on the samples used, thus making higher precision estimation very costly. In this paper, we suggest and investigate a multilevel Monte Carlo approach which uses a multigrid hierarchy to stochastically estimate the trace. This results in a substantial reduction of the variance, so that higher precision can be obtained with much less effort. We illustrate this for the trace of the inverse using three different classes of matrices.