3 ms·
The title of this article is pretty dubious given the relative improvement. For a 3x3 matrix, the naive approach requires 2^3 multiplications. The theoretical
by SeanAnderson 3y ago
The title of this article is pretty dubious given the relative improvement.
For a 3x3 matrix, the naive approach requires 2^3 multiplications. The theoretical ideal lowest bound is 2^2.
In 2020, our best was 2^2.3728596 and now our best is 2^2.371552... so, less than half a percent of an improvement
- Someone 3y ago> For a 3x3 matrix, the naive approach requires 2^3 multiplications 3^3. For a n×n matrix, it takes n^3. > The theoretical ideal lowest bound is 2^2. No, we know the exponent is at least 2, not that it is 2. I also think nobody thinks the exponent is 2, as that would mean we can multiply matrices with a single multiplication per value in the result (in this field, there isn’t even a “up to a constant factor” involved) Having said that, I think everybody thought the exponent was 3 until Strassen decreased it to 2log7.
- SeanAnderson 3y ago> No, we know the exponent is at least 2, not that it is 2. From the article: "bringing it closer to the ideal value of 2, which represents the theoretical minimum number of operations needed." It's fine if the article is wrong. You sound informed. Just wanted to highlight the difference.
- kadoban 3y agoThe nuance here is that the best _proven_ lower bound is n^2. ~Everybody suspects that the real lower bound is higher, but nobody seems to know how to prove it.