patternMinor
Computing tr(ABCD...)
Viewed 0 times
abcdcomputingstackoverflow
Problem
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
$$\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
Solution
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.
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.
Context
StackExchange Computer Science Q#145700, answer score: 2
Revisions (0)
No revisions yet.