Matrix multiplication in O(n^2.373)

http://www.scottaaronson.com/blog/?p=839

by davepeck • 15 years ago

166 52 15 years ago

wbhart11• 15 years ago

Note that the bound (as given in the paper) is now even better than the one mentioned in this blog (and the title).

This is of course huge news after twenty years of people trying to crack this.

You need matrices of dimension 1.66x10^91 before this result yields half the number of steps. But if an algorithm exists which made effective omega = 2 then this could have huge implications. So any improvement in techniques, no matter how slight, is very welcome, as it may lead to much more significant improvements later on.

kingkilr• 15 years ago

What's the constant factor look like? I know the previous asymptotically best matrix multiplication algorithm had such a high one as to render it useless in real world computations.

Rickasaurus2• 15 years ago

So now we know that the bound is at least 2.3727. Is it safe to assume that as they use higher and higher tensor powers the bound will shrink asymptotically toward the real bound?

wbhart11• 15 years ago

You mean at most 2.3727. It's not really a safe assumption that the bound will shrink asymptotically to the real omega as far as I know. But it is suspected that higher tensor powers may drop the exponent slightly.

I believe there are approaches related to other constructions in group theory, such as the wreath product, which may eventually lead to better results. It's just a huge unknown at this point. (My knowledge of these techniques can be written on the back of a postage stamp otherwise I'd try and provide more detail.)

One certainly hopes that higher and higher tensor powers are not the way to get omega = 2, as the algorithms just become more and more complex.

Someone may correct me if I am wrong but I think it is still not known even what the best algorithm is which breaks matrices up into 3x3 and whether one exists with better complexity than Strassen even (which breaks the matrix up into 2x2). A huge number of CPU cycles have been used trying to find the best algorithm using a 3x3 decomposition.

wbhart11• 15 years ago

Actually, my statement about matrices of size 1.66x10^91 is misleading. As with Strassen this new bound is an asymptotic bound for the technique meaning that you technically need matrices of infinite size before you realise that complexity. Whilst you can take an algorithm such as Strassen and really work out how many steps it will take, it is less straightforward for the CW style algorithms how many steps it is going to take for a given matrix. So my comparison is very much an approximation just to give the flavour of how big the matrices likely have to be for this algorithm to make a difference.

FaceKicker2• 15 years ago

Based on skimming the "our contribution" section of the paper (page 2), it seems like this isn't a new algorithm, but rather a new analysis of the same algorithm (Coopersmith Winograd) that proves a tighter lower bound on its runtime.

Not that that's not a valuable contribution, but the linked article seems kind of misleading, unless I'm misunderstanding the paper...

seagaia• 15 years ago

+1 For someone helping us understand this - is there now an implementation (or could someone now given this paper, produce an implementation) that will run in this new time? Or is it just (as FaceKicker asked) a new analysis?

xyzzyz• 15 years ago

Most likely, it's not a practical algorithm, in the sense that it would yield practical time improvement only for unfeasibly large matrices. It does not matter for theorists, though -- for them it's still important result.

wbhart11• 15 years ago

That is sort of true. The approach to constructing an algorithm is not new, being essentially due to Coppersmith-Winograd. They used an algorithm A (which doesn't actually multiply matrices, but from which a matrix multiplication algorithm can be constructed) which yielded omega < 2.39. They noted in their own paper that if the second tensor power of algorithm A is used instead of A when constructing the matrix multiplication algorithm, they get the bound 2.376.

This paper analyses the 8th tensor power of the original algorithm A in what is really a tour-de-force and show that it leads to a better bound. So technically the algorithm (the eight tensor power of the original algorithm that CW used) was "known". The innovation here is showing that this is actually better for constructing a matrix multiplication algorithm than the original or second tensor power algorithms.

This paper is also of interest because it allows analysis of tensor powers of other algorithms. It's probably just the beginning of a slew of new records.

There is no question this is a landmark paper. There has been an enormous amount of work for a very long time on this subject.

For those with infinite patience, there is a slightly simplified version of CW presented here:

http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/MAnd...

FaceKicker2• 15 years ago

> There is no question this is a landmark paper. There has been an enormous amount of work for a very long time on this subject.

I don't doubt that at all (though I personally know nothing about the field), I was only criticizing the linked article.

Rickasaurus2• 15 years ago

I skimmed the whole paper and came to the same conclusion. Seeing the general approach to analysis is interesting though, at least to a CompSci BA like me.

pantaloons• 15 years ago

A bit of a shallow point, but will anyone ever actually implement this algorithm?

I'm having trouble seeing the value of such a paper -- the size of matrices required for this result to have a clear advantage is significant, and that is completely ignoring constant factors, real world performance and parallelization considerations.

neeleshs• 15 years ago

Not sure what sizes apply here, but there are cases (many ML algos use large matrices) where this can be useful. Agree on the parallelization considerations, though.

jey• 15 years ago

No, these algorithms are impractical, but their utility is in shedding more light on the matrix multiplication problem. So it enables further study, which could lead to more practical advances.

dj_axl• 15 years ago

Right, from what I can tell the Strassen algorithm has been implemented but the others are typically pseudocode only...

http://stackoverflow.com/questions/1920031/strassens-algorit...

pluies_public• 15 years ago

For those of us a bit light on the theoretical CS aspect, is this article ironical? It sounds like quite a small improvement...

to3m• 15 years ago

See comment #16 on the linked-to page.

burgerbrain• 15 years ago

It is not ironic.

_mrc• 15 years ago

The difference between n^2.373 and n^2.376 (i.e. n^0.003) is about 1.3% for n=100, 2% for n=1000, and keeps getting better for large n.

http://www.wolframalpha.com/input/?i=n%5E2.373%2Fn%5E2.376%2...

wbhart11• 15 years ago

Except that this algorithm can't be used for anything as small as n = 100. Essentially the analysis is asymptotic, meaning that you have matrices of dimension n = q^N and let N tend towards infinity to get your bound on omega.

LokiSnake• 15 years ago

When you start applying real numbers to n, using O() doesn't make sense. When comparing the two in a slightly practical sense, the constant factor has to be taken into account.

alex-g• 15 years ago

The author, Virginia Vassilevska Williams, is married to Ryan Williams, who last year proved a major result in circuit complexity lower bounds (NEXP is not contained in ACC0). It's interesting to see that both of them are making important discoveries, in different areas of computational complexity.

antics2• 15 years ago

A bit more context: Scott Aaronson called Ryan Williams' discovery "one of the best of the decade". He recently got hired as professor at Stanford, and his advisor was the legendary Manuel Blum, who teaches at CMU, where both his wife and son are also tenured CS professors.

greeneggs• 15 years ago

A bit more context: Stanford did not hire Virginia Williams, and she is looking for a job. Academic hiring in CS departments is driven by tweets. Hence the sensational blog post. /cynic (I do wish her luck.)

spaznode2• 15 years ago

Forgive my ignorance, but does anyone know any real world examples where something like this might improve a certain type of work?

I'm sort of fuzzily half-assedly thinking this might be applicable to image - and by extension video - work but maybe that's not the case at all. I want to be more excited, please enlighten me. :)

mattdeboard• 15 years ago

You are probably about as excited about this as people in the 20s and 30s were about quantum theory. "Immediate practical impact" is not how one qualifies research, at least not from my perspective.

spaznode2• 15 years ago

That's a perfectly good response. Just wanted to know if this was a "people quietly shuffling and re-implementing some core algo" kind of announcement or more general scientific theory.

So, thank you. By all means keep researching and advancing.

_delirium• 15 years ago

Faster matrix multiplication in general is an important applied topic, because it can speed up all sorts of scientific, engineering, and ML algorithms that have it as a step (often one of the bottleneck steps). However this new technique appears to be more of theoretical interest because of how impossibly large the matrices would have to be before it becomes faster than simpler techniques.

The Strassen algorithm (http://en.wikipedia.org/wiki/Strassen_algorithm) is used in practice though, and is faster than the naive multiplication approach for moderately large matrices, so this kind of research sometimes produces practical speedups. Not in this case without significant further breakthroughs to really bring down the size of matrices that it wins on, though.

damoncali• 15 years ago

Finite Element Analysis. Maybe. In theory. There are lots of very large square matrices used in the various problems solved by the method. The limit of the technique is generally computing time, although last I worked in the field (about 10 years ago), we were using way, way smaller matrices than are being discussed here, and I don't recall how often the limiting factor was multiplying two of them together. (The usual case is a simple {x} = [M] * {v}).

But I always wondered what FEA would look like if we removed the constraint of model size and computing power.

flourpower• 15 years ago

I couldn't find this by googling - if A is an n by n matrix, can you get A^k strictly faster than you can get a product of k arbitrary n by n matrices?

zheng• 15 years ago

Yes, see the Cayley-Hamilton Theorem[1], which changes matrix powering into the powering of scalers in the characteristic polynomial.

[1] http://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem

wbhart11• 15 years ago

Ah yes, one can compute P(x) a polynomial such that P(A) = 0. If you wish to compute A^n for n much bigger than the degree of P you can compute S(x) = x^n mod P(x) and then just compute S(A).

However, algorithms that do actually improve the complexity of powering when this technique isn't applicable do exist. Here is a paper on a recent one:

http://marco.bodrato.it/papers/Bodrato2010-StrassenLikeMatri...

Rhapso• 15 years ago

Just spending 30 seconds looking at it, think of it like the bit shifting solution to multiplication, do a related faster operation then correct.

You can reduce A^k to be a lot faster if you calculate A^2 then A^4 then A^8 .. A^N where N is 2^(Log(k)-1) (log base 2) then multiply A^N by A^(k-N) (which you can speedup using the same method if it is larger then 4)

That was a bit rough and quick, but the basic idea, is that doing (nxn)^k would likely be reduced to O(log(k)n^2.373) versus the more naive O(kn^2.373) which is a speedup of O(k/log(k)) (or it's inverse, I am not sure how it is best to represent the ratio) which is decent, I am sure there is a better solution out there.

wbhart11• 15 years ago

Multiplying k arbitrary matrices can be done in less time than O(kn^omega). But certainly for k > 3 you wouldn't multiply naively k times as you've pointed out.

dbbo3• 15 years ago

So, it's a blog post that announces a paper. Why not just post the link to the paper?

corysama• 15 years ago

The layman terms background and summary adds a lot of value for the non-mathematicians in the audience.

dbbo3• 15 years ago

I can't imagine why anyone would want to pander to non-mathematicians.

wging2• 15 years ago

As smart as the Hacker News set may be, most people are not experts in the field and could do with a little context.

Also, Aaronson's a well-known computer scientist, so this helps establish that the result's both credible and important in the eyes of people who may not (forgive me) all be qualified to judge the paper on its merits.

dbbo3• 15 years ago

Context: fair point. I can't say I'm familiar with Aaronson, however (of course I studied math and not CS).

amund• 15 years ago

The lower bound is Omega(n^2 lg n), but waiting for an algorithm (if there is one). Ref: Ran Raz - http://dl.acm.org/citation.cfm?id=944299 (similar complexity for Matrix Inversion due to the relationship between matrix inversion and multiplication, ref Introduction to Algorithms, 1st ed, pp 762-765, wrote the proof here http://amundtveit.info/publications/2003/ComplexityOfMatrixI...)

ot• 15 years ago

For those interested in the details, the (excellent, as always) blog of Richard Lipton sheds some light

http://rjlipton.wordpress.com/2011/11/29/a-breakthrough-on-m...

Matrix multiplication in O(n^2.373)

Related Stories