# Memory efficient matrix multiplication

What is the most memory efficient algorithm for calculating $A\cdot B$, where $A,B\in \mathbb{R}^{n \times n}$?
The result of this multiplication might be stored in one of the given matrices ($A$ or $B$). The 'ideal' algorithm would perform calculations with $O(1)$ additional memory and return $A\cdot B$ and $B$

-
Any specific motivation for this question? Or some background that might be helpful? –  Suvrit Jan 21 '11 at 15:44
@Survit: Recently I've been working on some econometric models where data might change. It is highly inefficient to calculate erverything from the scrath, so I was thinking about some better way and I found it for some special case of 'very' sparse matrix. That made me think about more generale case. –  Tomek Tarczynski Jan 21 '11 at 17:25

## 2 Answers

This may help.

-
@alpoge: I haven't read this article, just a quick look on the conclusions but it seems that it might be helpful. I found such a sentence "If the input matrices can be overwritten, we proposed a fully in-place schedule for the operation C ← A × B with - out any extra operations." Without reading whole article I can't tell whether they meant extra space apart from A and B or apart from A,B and C. Strassen-Winograd’s algorithm might (this is just an oppinion, I need to read more about this algorithm) need even more memory than the naive algorithm. –  Tomek Tarczynski Jan 21 '11 at 17:39
Well, from their abstract: "In particular, we show two fully in-place schedules: one having the same number of operations, if the input ma- trices can be overwritten; the other one, slightly increasing the constant of the leading term of the complexity, if the input matrices are read-only" –  alpoge Jan 21 '11 at 18:27

I don't know if $O(1)$ is possible, but $O(n)$ obviously is. Since $n=o(n^2),$ this is good enough for any practical purpose, if you are multiplying dense matrices. If your matrices are not dense, you can do better, but how much better, and how, obviously depends on the problem, so we are back to @Suvrit's question.

-