<p>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$. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-02-14T09:30:01.857Z
[SC](https://en.wikipedia.org/wiki/SC_(complexity)).
Kaveh
CC BY-SA 3.0
2016-02-14T10:39:13.273Z
Specifically, the question is equivalent to the open problem $\mathrm{DET}\subseteq\mathrm{SC}$.
Emil Jeřábek
CC BY-SA 3.0
2016-02-14T21:27:53.183Z
@EmilJeřábek what are consequences of $DET\subseteq SC$? Is there a reference for this problem?
Turbo
CC BY-SA 3.0
2016-02-15T01:14:16.833Z
@EmilJeřábek, thanks! I am wondering what's the reduction from it to DET? Can you provide some reference for that?
Lijie Chen
CC BY-SA 3.0
2016-02-15T17:22:57.483Z
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, ...
Emil Jeřábek
CC BY-SA 3.0
2016-02-15T17:23:38.970Z
... 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.)
Emil Jeřábek
CC BY-SA 3.0
2016-02-16T00:32:35.630Z
@EmilJeřábek, now I got it. really thanks for the helpful comment! This is equivalent in the sense of poly(n,m), but not m*poly(n) though.
Lijie Chen
CC BY-SA 3.0
2016-02-16T11:49:33.163Z
That's right, however it appears the expected answer is negative, in which case it would also rule out the more strict reduction.
Emil Jeřábek
<lower-bounds><matrix-product><space-complexity>
Space complexity for multiplying $m$ matrices
Lijie Chen
# Space complexity for multiplying $m$ matrices

(Asked by: username_0 on 2016-02-14)

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.

**Tags:** lower-bounds, matrix-product, space-complexity
> **Comments:**
> **username_1**: [SC](https://en.wikipedia.org/wiki/SC_(complexity)).  
> **username_2**: Specifically, the question is equivalent to the open problem $\mathrm{DET}\subseteq\mathrm{SC}$.  
> **username_3**: @EmilJeřábek what are consequences of $DET\subseteq SC$? Is there a reference for this problem?  
> **username_0**: @EmilJeřábek, thanks! I am wondering what's the reduction from it to DET? Can you provide some reference for that?  
> **username_2**: 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, ...  
> **username_2**: ... 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.)  
> **username_0**: @EmilJeřábek, now I got it. really thanks for the helpful comment! This is equivalent in the sense of poly(n,m), but not m*poly(n) though.  
> **username_2**: That's right, however it appears the expected answer is negative, in which case it would also rule out the more strict reduction.  

---

## 0 answers

