3
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Any specific motivation for this question? Or some background that might be helpful? $\endgroup$
    – Suvrit
    Jan 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$ Jan 21, 2011 at 17:25

2 Answers 2

2
$\begingroup$

This may help.

$\endgroup$
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$
    – alpoge
    Jan 21, 2011 at 18:27
  • $\begingroup$ Sadly, link is dead. $\endgroup$
    – PythonNut
    Oct 21, 2017 at 20:20
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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