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$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Any specific motivation for this question? Or some background that might be helpful? $\endgroup$– SuvritJan 21, 2011 at 15:44
-
$\begingroup$ @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. $\endgroup$– Tomek TarczynskiJan 21, 2011 at 17:25
Add a comment
|
2 Answers
3
-
$\begingroup$ @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. $\endgroup$ Jan 21, 2011 at 17:39
-
$\begingroup$ 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" $\endgroup$– alpogeJan 21, 2011 at 18:27
-
$\begingroup$
$\endgroup$
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.