Hierarchical Probing for Estimating the Trace of the Matrix Inverse on Toroidal Lattices

The standard approach for computing the trace of the inverse of a very large, sparse matrix $A$ is to estimate it through the Monte Carlo algorithm as the mean value of matrix quadratures. This is heavily used in our motivating application of Lattice QCD. Often, the elements of $A^{-1}$ display certain decay properties away from the nonzero structure of $A$, but random vectors cannot exploit this induced structure of $A^{-1}$. Probing is a technique that discovers elements of a matrix $A$ through matrix-vector multiplications by using vectors tailored to the sparsity pattern of the matrix. In the case of $A^{-1}$, and when the above decay properties are present, the pattern is obtained by distance-$k$ coloring of the graph of $A$, in which no nodes within distance $k$ of each other have the same color. For sufficiently large $k$, the method produces accurate trace estimates but it becomes expensive and in some cases prohibitive. More importantly, it is difficult to search for an optimal $k$ value, since n...