# Parallel, matrix-free estimate of the trace

What would be the best way to estimate the trace of a large, distributed matrix, if one only know its action on a vector throug a parallel "matvec" routine?

In the application I am interested in, the matvec routine comes from the discretization of a PDE. In most cases, I cannot modify this routine.

I do not need machine precision and would be satisfied with moderate accuracy.

• Would applying the operator the identity matrix work? May 31 '20 at 22:20
• Yes, but it would require O(n) matvec for a n by n matrix which I fear is intractable. May 31 '20 at 22:32
• I was thinking about n matvec operations that can be parallelized. But if that's "intractable" for you, I think that would go into the question. May 31 '20 at 22:41
• How about stochastic/heuristic methods? For example, Hutchinson's trick; an accessible write up at the link: blog.shakirm.com/2015/09/… . I don't know if that is tractable for your application though. You need to sample some number of vectors and do matvec and vecvec multiplications. May 31 '20 at 23:45
• @Abdullah Ali Sivas: Thanks for the suggestion. I will consider this method. That being said, what I had in mind was a method that would directly link the matvec operation with an estimate of the trace (or any power-iteration/arnoldi like method). Jun 1 '20 at 1:33

First, for most sparse matrices you don't actually need $$n$$ matvecs with unit vectors to determine the diagonal entries. Rather, if you know the sparsity pattern, you can "color" the nodes in your discretization so that nodes of the same color do not couple in the matrix. As a consequence, you should be able to compute the trace of the matrix with something like $${\cal O}(10-100)$$ matvecs, independent of the size of the matrix (but depending on the kind of discretization you are using).