The solution to this problem can be found here. It says:

To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of the first $k − 1$ and the $tj$th entry in the last matrix. Inductively, we need to maintain $k$ counters which can be done in $O(k \log n)$ space. Finally, note that using repeated squaring, we can compute $A^p$ using $O(\log p)$ matrices, which are different powers of $A$. To generate each of these matrices, we just need $A$ and a single counter. Hence the total space needed is $O(\log p \log n)$.

What I don't understand is that in the case of multiplying $k$ fixed matrices, they're part of the input tape so no space is needed for them in the work tapes. In the case of the $A^p$ computation, the intermediate results $A^{2^t}$ must be stored somewhere demanding more space. So how can this be done in $O(\log p \log n)$ space?



No. The intermediate matrices $A^{2^t}$ don't need to be stored anywhere. When you need a value, you just recompute it. This might sound very inefficient -- but remember, we're only counting the space complexity here, not the time complexity, so it's fine to take a very long time to recompute the same value many times, if that saves you some space.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much for your kind reply. If the intermediate matrices don't need to be stored anywhere, I don't understand the algorithm that let compute $A^p$ in $O(\log n\log p)$ space. $\endgroup$ – Pierrot Dec 10 '19 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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