Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

share|improve this question
    
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 2

up vote 2 down vote accepted

This may help.

share|improve this answer
    
@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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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