  The standard approach for computing the trace of the inverse of a very large,
sparse matrix $A$ is to view the trace as the mean value of matrix quadratures,
and use the Monte Carlo algorithm to estimate it. This approach is heavily used
in our motivating application of Lattice QCD. Often, the elements of $A^{-1}$
display certain decay properties away from the non zero structure of $A$, but
random vectors cannot exploit this induced structure of $A^{-1}$. Probing is a
technique that, given a sparsity pattern of $A$, discovers elements of $A$
through matrix-vector multiplications with specially designed vectors. In the
case of $A^{-1}$, the pattern is obtained by distance-$k$ coloring of the graph
of $A$. For sufficiently large $k$, the method produces accurate trace
estimates but the cost of producing the colorings becomes prohibitively
expensive. More importantly, it is difficult to search for an optimal $k$
value, since none of the work for prior choices of $k$ can be reused.
