# How to stochastically estimate the trace of a matrix?

Specifically, the diagonal elements (can possibly both positive and negative) of the matrix can be computed efficiently but the total number is large ($\mathcal O(10^{18})$).

My first thought about this was running an MCMC (Markov Chain Monte-Carlo) with the weight set to be the absolute value of each element; however, this just exactly leads to the sign problem. But I'm still wondering if there is any smart way to tackle that.

• It's not clear what you mean by " the diagonal elements [...] of the matrix can be computed efficiently but the total number is impossible to enumerate." If the diagonal elements can be computed efficiently, then the trace (i.e., the sum of the diagonal elements) should be easy to compute. But what do you mean by "total number" and "enumerate"? – Wolfgang Bangerth Jun 8 '17 at 19:23
• @WolfgangBangerth Sorry for the ambiguity and let me make it clear. My matrix is huge(10^18) thus it's impossible to sum up all diagonal elements by brute force. But for any basis vector, the corresponding diagonal element can be calculated efficiently. – Izzy Vang Jun 8 '17 at 20:10
• Update the question with that information then – nicoguaro Jun 9 '17 at 3:57
• I still don't get it. Surely one can't expect to compute the trace with fewer than $n$ operations, which is what it would cost if you just summed up the diagonal entries given that they're easily computable. But even then, just doing $O(n)$ operations with $n=10^{18}$ is a proposition that stretches today's computers -- it corresponds to at least $10^9$ CPU seconds, or $300,000$ CPU hours, or $1000$ CPU years, times the number of cycles necessary to compute a matrix element. Good luck with that. – Wolfgang Bangerth Jun 9 '17 at 4:25
• I think what you want is something like this arxiv.org/abs/1608.00117 (which I found as the first Google hit for "stochastic trace estimation"...) – Christian Clason Jun 9 '17 at 6:39