2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would applying the operator the identity matrix work? $\endgroup$ – nicoguaro May 31 at 22:20
  • $\begingroup$ Yes, but it would require O(n) matvec for a n by n matrix which I fear is intractable. $\endgroup$ – Christine Darcoux May 31 at 22:32
  • $\begingroup$ 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. $\endgroup$ – nicoguaro May 31 at 22:41
  • 3
    $\begingroup$ 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. $\endgroup$ – Abdullah Ali Sivas May 31 at 23:45
  • $\begingroup$ @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). $\endgroup$ – Christine Darcoux Jun 1 at 1:33
1
$\begingroup$

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).

But it might be even cheaper to use a randomized algorithm to estimate the trace. I don't have a reference at hand, but if you search for "randomized algorithm for estimating the trace of a matrix" you will find some.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The blog post referenced in the comments to the question does a decent job introducing randomized trace estimators and giving a couple key citations. $\endgroup$ – cdipaolo Jun 1 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.