3
$\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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Would applying the operator the identity matrix work? $\endgroup$
    – nicoguaro ♦
    Commented May 31, 2020 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
    Commented May 31, 2020 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 ♦
    Commented May 31, 2020 at 22:41
  • 4
    $\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
    Commented May 31, 2020 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
    Commented Jun 1, 2020 at 1:33

1 Answer 1

Reset to default
2
$\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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Jun 1, 2020 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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