CanadaPlus , 1 month ago (edited 1 month ago)

Yeah, they work by turning the problem into some crazy kind of group theory and attacking it that way. Every once in a while someone shaves the decimal down slightly, just by implementing the deep math in a more efficient way. A new approach will be needed if it is in fact possible to get down to O(n^2^), though. Strassen’s is a divide and conquer algorithm, and each step of the iteration looks like this:

<span style="color:#323232;">    S[1] = B[1, 2] - B[2, 2]
</span><span style="color:#323232;">    S[2] = A[1, 1] + A[1, 2]
</span><span style="color:#323232;">    S[3] = A[2, 1] + A[2, 2]
</span><span style="color:#323232;">    S[4] = B[2, 1] - B[1, 1]
</span><span style="color:#323232;">    S[5] = A[1, 1] + A[2, 2]
</span><span style="color:#323232;">    S[6] = B[1, 1] + B[2, 2]
</span><span style="color:#323232;">    S[7] = A[1, 2] - A[2, 2]
</span><span style="color:#323232;">    S[8] = B[2, 1] + B[2, 2]
</span><span style="color:#323232;">    S[9] = A[1, 1] - A[2, 1]
</span><span style="color:#323232;">    S[10] = B[1, 1] + B[1, 2]
</span><span style="color:#323232;">    P[1] = STRASSEN(A[1, 1], S[1])
</span><span style="color:#323232;">    P[2] = STRASSEN(S[2], B[2, 2])
</span><span style="color:#323232;">    P[3] = STRASSEN(S[3], B[1, 1])
</span><span style="color:#323232;">    P[4] = STRASSEN(A[2, 2], S[4])
</span><span style="color:#323232;">    P[5] = STRASSEN(S[5], S[6])
</span><span style="color:#323232;">    P[6] = STRASSEN(S[7], S[8])
</span><span style="color:#323232;">    P[7] = STRASSEN(S[9], S[10])
</span><span style="color:#323232;">    C[1..n / 2][1..n / 2] = P[5] + P[4] - P[2] + P[6]
</span><span style="color:#323232;">    C[1..n / 2][n / 2 + 1..n] = P[1] + P[2]
</span><span style="color:#323232;">    C[n / 2 + 1..n][1..n / 2] = P[3] + P[4]
</span><span style="color:#323232;">    C[n / 2 + 1..n][n / 2 + 1..n] = P[5] + P[1] - P[3] - P[7]
</span><span style="color:#323232;">    return C
</span>

In my copy of Introduction to Algorithms, it says something like “this is the most bullshit algorithm in the book and it’s not close” underneath. You can make it a bit neater by representing the multiplication operation as a 3-dimensional tensor, but at the end of the day it’s still just a stupid arithmetic trick. One that’s built into your GPU.