6
$\begingroup$

Suppose we have $k$ $n\times n$ matrices $A,B,C,\ldots$. Is there a way to compute/approximate the trace of their product much faster than computing/approximating the full matrix product? IE, computing

$$\text{tr}(ABC\ldots)$$

A related problem of computing vector matrix product $v'ABC$ can be done in $O(n^2)$ time by skipping most of the computation needed for the full matrix product, so I'm wondering if there's a trick to speed up the trace as well

Improve this question
$\endgroup$
4
  • $\begingroup$ By any chance, is the resulting matrix symmetric? Then could compute $v^\top ABC \ldots v$ for $v \sim \mathcal N(0^n, I_n))$, and your expectation should be the trace, unless I made a mistake. $\endgroup$
    – Dmitry
    Nov 15, 2021 at 11:32
  • $\begingroup$ Yes, that works (even for nonsymmetric), but it's not clear this is better than approximating full matrix product in a similar way, just put v's in the middle: AB...Cvv'DE.. is equal to the matrix product in expectation $\endgroup$
    – Yaroslav Bulatov
    Nov 16, 2021 at 22:29
  • $\begingroup$ Should be the same, by the cyclic property of trace: $tr(AB...Cvv'DE..F)=tr(v'DE..FAB...Cv)$. But it already gives you the solution, no? (product of Gaussians should have decent concentration) $\endgroup$
    – Dmitry
    Nov 17, 2021 at 7:30
  • $\begingroup$ So here it seems that approximating trace has same cost as approximating the matrix product, since you can view this trick as taking trace of the matrix product approximation. I was curious if trace is fundamentally easier than full matrix product (like is the case with vector/matrix product), which seems like it isn't $\endgroup$
    – Yaroslav Bulatov
    Nov 17, 2021 at 20:08

1 Answer 1

Reset to default
2
$\begingroup$

For the worst-case time complexity, no algorithm faster than $\Theta(n^{\omega})$ time is known, even for the approximation version.

Indeed, there is a simple reduction from the triangle counting problem to the trace computation of a product matrix. Let $A$ be an adjacent matrix of an undirected graph, then $\mathrm{tr}(A^3)/2$ is the number of triangles of the graph. Note that this reduction preserves approximation factors.

As far as I know, this is the best-known way to count triangles in dense graphs. I don't have a proper reference but see this question on TCS.SE https://cstheory.stackexchange.com/questions/48539/fastest-approximate-triangle-counting-algorithms-in-dense-graphs for example.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, connection to triangle counting is a useful to know $\endgroup$
    – Yaroslav Bulatov
    Dec 15, 2021 at 18:52

Your Answer

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

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