Timeline for Why is fast matrix multiplication impractical?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30, 2022 at 19:00 | comment | added | Cort Ammon | @WillSawin From that phrasing, I would agree. A single application of Strassen's algorithm saves 12.5%. Iterating it twice saves more. The asymptotic limit given in big-O notation is always the limit of this process. The tricky bit is that each iteration applies only to a matrix that's 2x bigger in each direction. So these 12.5% boons appear further and further apart as n gets large. | |
| Apr 30, 2022 at 9:25 | comment | added | kaya3 | You save 1/8 at each level, but also the levels are exponentially smaller because of the savings from the above levels. | |
| Apr 30, 2022 at 2:53 | comment | added | Charles | A 2-layer Strassen with element multiplication and addition taking the same time (not crazy say, over a finite field) exceeds a factor of 7/8 at 256x256. | |
| Apr 30, 2022 at 2:09 | comment | added | Will Sawin | @Kevin This is absurd - if that were true, the asymptotic savings of Strassen's algorithm would itself be by a factor of $7/8$, and not by a factor of $n^{ \log (7/8) / \log 2}$, as it is. | |
| Apr 30, 2022 at 2:02 | comment | added | Kevin | @WillSawin: The brute force algorithm is also recursive (or at least, it is equivalent to a recursive version). You save 1/8 at each level, but that's equivalent to saving 1/8 overall. | |
| Apr 30, 2022 at 1:56 | comment | added | Will Sawin | @Kevin Sure, but each multiplication can itself be achieved by doing 7 multiplications instead of the brute force 8, so you save another $1/8$ (asymptotically). The question is only how much of the asymptotic savings can be achieved at practical values. I would be very surprised if the answer is exactly equal to the maximum theoretical savings from doing only one iteration, given that multiple iterations are viable in practice! | |
| Apr 30, 2022 at 1:39 | comment | added | Kevin | @WillSawin: The brute force algorithm is equivalent to doing 8 multiplications, and Strassen manages it in 7, so you save 1/8 of the work (the additions are linear and therefore dominated by the multiplications). | |
| Apr 30, 2022 at 0:36 | comment | added | Will Sawin | @CortAmmon With that definition of Strassen's algorithm, which I agree is better, my question can be shortened to "Surely Strassen's algorithm can save more than $12.5\%$ if $n$ is large?" - can you really give a negative answer? | |
| Apr 29, 2022 at 17:54 | comment | added | Cort Ammon | @WillSawin That is not possible because Strassen's algorithm is already a nested algorithm, which is how we get to the O(...) bound described. You continue to use Strassen's algorithm on the sub blocks until it reaches a threshold where it is more efficient to switch back to brute force. The literature I've seen shows that Strassen's starts to be a better choice around 1024x1024, so said 1024x1024 matrix would use this breakdown once before switching to brute force. A 2048x2048 might use it twice before switching. | |
| Apr 29, 2022 at 13:13 | comment | added | Will Sawin | Surely Strassen's algorithm can save more than $12.5\%$ if $n$ is so large that nested Strassen is viable? | |
| Apr 29, 2022 at 12:03 | history | answered | gnasher729 | CC BY-SA 4.0 |