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$
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.



This may help. 


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. 

