4
$\begingroup$

Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$.

The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. I am wondering can there be any algorithm with $polylog(n,m)$ memory but still $m \cdot poly(n)$ or $poly(n,m)$ running time. It sounds like an old problem but I couldn't find any reference.

Note that using the divide and conquer technique (like in Savitch's theorem), we can achieve $polylog(n,m)$ memory and $m \cdot n^{O(\log m)}$ running time.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ SC. $\endgroup$
    – Kaveh
    Commented Feb 14, 2016 at 9:30
  • 4
    $\begingroup$ Specifically, the question is equivalent to the open problem $\mathrm{DET}\subseteq\mathrm{SC}$. $\endgroup$
    – Emil Jeřábek
    Commented Feb 14, 2016 at 10:39
  • 1
    $\begingroup$ @EmilJeřábek, thanks! I am wondering what's the reduction from it to DET? Can you provide some reference for that? $\endgroup$
    – Lijie Chen
    Commented Feb 15, 2016 at 1:14
  • 2
    $\begingroup$ The original reference is Cook, A taxonomy of problems with fast parallel algorithms, Information and Control 64 (1985), 2–22. The reduction is actually not hard to sketch. First, you can reduce matrix inverse to determinant using Cramer’s rule. Second, let $M$ denote the $n(m+1)\times n(m+1)$ matrix, considered as $(m+1)\times(m+1)$ blocks of $n\times n$ matrices, in which the superdiagonal blocks are $M_1,\dots,M_m$, and the rest are $0$. Since $M$ is nilpotent ($M^{m+1}=0$), we have $(I-M)^{-1}=I+M+M^2+\dots+M^m$, and one can check that the block in the top-right corner of this inverse, ... $\endgroup$
    – Emil Jeřábek
    Commented Feb 15, 2016 at 17:22
  • 1
    $\begingroup$ ... coming from the $M^m$ summand, equals the desired product $M_1\cdots M_m$. (BTW, note that the matrix being inverted here has determinant $1$, hence no division is needed in this application of Cramer’s rule.) $\endgroup$
    – Emil Jeřábek
    Commented Feb 15, 2016 at 17:23

1 Answer 1

Reset to default
2
$\begingroup$

Letting m be [number of vertices minus 1] and letting each matrix be
[the adjacency matrix of the result of giving the vertex t a loop]
gives a reduction from st-connectivity to your problem, so no such algorithm is known.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! This is one of my motivation to think about this problem! Actually I tend to believe that there can't be such algorithm. But it seems quite hard to prove. $\endgroup$
    – Lijie Chen
    Commented Feb 15, 2016 at 1:14

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.