Tuesday, January 13, 2015
Barrier's for Matrx Mult Lower bound
Matrix Mult:
The usual algorithm is O(n^3).
Strassen surprised people by showing an O(n^{2.81}) algorithm. (Now its so well known that its not surprising. I try to teach it to people who don't already know its true so they'll be surprised.)
Over the years the exponent came down, though there was a long time between Coopersmith and Winograd's exp of 2.3755 and the recent improvements.
Are these improvements going to lead to the exp 2+epsilon?
Alas the answer is prob no :-(
In Fast Matrix Mult: Limitations of the Laser Method Ambainis, Filmus, and Le Gall show that the methods that lead to the algorithms above will NOT lead to an exp of 2+epsilon.
How to react to news like this? Barriers should not make us give up; however, they should make us look for new techniques, perhaps guided by the barrier. I would like to think that if you know where NOT to look then it helps you know where TO look.
There have been barriers that were broken (IP=PSPACE didn't relativize, the recent 2-prover PIR used techniques NOT covered by the barrier result, and the Erdos distance problem was proven after it was known that the current techniques `wouldn't work'). I am sure there are other examples, feel free to leave some in the comments
Will this result help guide researchers in the right direction? Lets hope so!
Of course, its possible that 2+epsilon is false and the barrier result is a first step in that direction.
Which one am I routing for? Neither- I am routing for finding out!
bill g.
Subscribe to:
Post Comments (Atom)
I am surprised by two parts of you post:
ReplyDelete1. I would not call the O(n³) algorithm the "usual" one, maybe the classical one or the schoolbook algorithm.
2. "Alas the answer is prob no :-(": Of course, the barrier provided by the recent paper you mention shows that one needs new techniques to hope going down to O(n^(2+eps)), and especially in regards of the recent improvements of CW algorithm, I find this result remarkable. But since there has been several distinct techniques to attack MM over the years, I wouldn't be surprised at all if somebody brings a new technique to the domain!
(This is BIll Gasarch, I was in a diff gmail account when I responded)
Delete1) I thought the O(n^3) alg was the one people usually used? Its a good question what is used usually- perhaps one could do a survey of linear algebra packages and see what is used most often.
2) Lets hope you're right!
1) For instance, the LinBox package for linear algebra (in particular included in Sage) uses Strassen-Winograd's algorithm and even Bini's one. This recent paper (and its bibliography) gives some details: https://hal.archives-ouvertes.fr/hal-00987812/.
Delete2) Of course I am! (Easier to say that as an anonymous ;-)).
For the sake of students like me - can someone briefly spell out exactly what is meant by "2+epsilon"?
ReplyDeleteThanks in advance :)
I tend to think of the "+epsilon" as meaning "plus a little bit more that can't be zero and the smaller the epsilon is the larger the multiplicative constant the "O of" isn't showing becomes.
DeleteGood question- we sometimes are so used to how we talk about things we forget that there are students out there who don't quite know the lingo yet.
ReplyDelete``We can multiply matrices in n^{2+epsilon}'' means
for all \delta>0 there is an algorithm that will multiply matrices in time O(n^{2+\delta}).''
so we can get as close to n^2 as we want, though the mult constant might grow--- it might
depend on delta.
No post is complete without a spelling error: "routing" => "rooting"
ReplyDeleteBTW, why shoot for exponent 2+\epsilon? Is it impossible for the exponent to be 2?
See the discussion in http://cstheory.stackexchange.com/questions/9186/definition-of-matrix-multiplication-exponent-omega
Delete