The asymptotically fastest algorithm for matrix multiplication takes time O(nω) for some value of ω. Here are the best known upper bounds on ω over time.
The latest improvements, the first in over 20 years, are due to Andrew Stothers and Virginia Vassilevska Williams. The latter gave an O(n2.3727)-time algorithm for multiplying matrices.
When will the sometimes-conjectured ω = 2 be reached? Certainly nothing wrong with taking a linear fit of this data, right?
So that would be around the year 2043. Unfortunately, the pessimist's exponential fit asymptotes to ω = 2.30041...
Posts
No comments:
Post a Comment