Skip to content

Instantly share code, notes, and snippets.

@thien
Created December 2, 2016 13:16
Show Gist options
  • Save thien/b8b9030c45336d74113fddcb4a011b64 to your computer and use it in GitHub Desktop.
Save thien/b8b9030c45336d74113fddcb4a011b64 to your computer and use it in GitHub Desktop.
Strassen's Algorithm for a 2x2 Matrix
x=[[0,2],[0,1]]
y=[[0,0],[3,4]]
def strassen(a,b):
S = [b[0][1] - b[1][1],
a[0][0] + a[0][1],
a[1][0] + a[1][1],
b[1][0] - b[0][0],
a[0][0] + a[1][1],
b[0][0] + b[1][1],
a[0][1] - a[1][1],
b[1][0] + b[1][1],
a[0][0] - a[1][0],
b[0][0] + b[0][1]]
P = [a[0][0] * S[0],
S[1] * b[1][1],
S[2] * b[0][0],
a[1][1] * S[3],
S[4] * S[5],
S[6]*S[7],
S[8]*S[9]]
C = [[P[4]+P[3]-P[1]+P[5],P[0]+P[1]],
[P[2]+P[3],
P[4]+P[0]-P[2]-P[6]]]
print(S)
print(P)
print(C)
strassen(x,y)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment