Matrix multiplication algorithms over time

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...

No comments:

Post a Comment