Strassen matrix multiplication in python

def matrix_addition(A, B):
# Check if matrices have the same size
if len(A) != len(B) or len(A[0]) != len(B[0]):
raise ValueError("Matrices must have the same size")
# Initialize result matrix with zeros
result = [[0 for col in range(len(A[0]))] for row in range(len(A))]
# Add matrices element-wise
for row in range(len(A)):
for col in range(len(A[0])):
result[row][col] = A[row][col] + B[row][col]
return result
def matrix_subtraction(A, B):
# Check if matrices have the same size
if len(A) != len(B) or len(A[0]) != len(B[0]):
raise ValueError("Matrices must have the same size")
# Initialize result matrix with zeros
result = [[0 for col in range(len(A[0]))] for row in range(len(A))]
# Subtract matrices element-wise
for row in range(len(A)):
for col in range(len(A[0])):
result[row][col] = A[row][col] - B[row][col]
return result
def strassen(a, b):
if len(A) == 1 and len(A[0]) == 1:
return a[0][0] * b[0][0]
else:
# divide into quadrants
quad1_a, quad2_a, quad3_a, quad4_a = divide(a)
quad1_b, quad2_b, quad3_b, quad4_b = divide(b)
#break into parts to compute 
p1 = strassen(matrix_addition(quad1_a, quad4_a), matrix_addition(quad1_b, quad4_b))
p2 = strassen(matrix_addition(quad3_a + quad4_a), quad1_b)
p3 = strassen(quad1_a, matrix_subtraction(quad3_b, quad1_b))
p4 = strassen(quad4_a, matrix_subtraction(quad3_b, quad1_b))
p5 = strassen(matrix_addition(quad1_a, quad2_a), quad4_b)
p6 = strassen(matrix_subtraction(quad3_a, quad1_a), matrix_addition(quad1_b, quad2_b))
p7 = strassen(matrix_subtraction(quad2_a, quad4_a), matrix_addition(quad3_b, quad4_b))
# create the final matrix
final_quad1 = matrix_subtraction(matrix_addition(p1, p4), matrix_addition(p5, p7))
final_quad2 = matrix_addition(p3, p5)
final_quad3 = matrix_addition(p2, p4)
final_quad4 = matrix_addition(matrix_subtraction(p1, p2), matrix_addition(p3, p6))
resultant_matrix = combine_submatrices(final_quad1, final_quad2, final_quad3, final_quad4)
return resultant_matrix

its a basic implementation of the strassen algorithm i have tested all the secondary function and they work but joined together i keep running into problems.

the strassen function is supposed to take 2 2d arrays of 2^n size for the above code i used the arrays

A = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
B = [[17, 18, 19, 20],
[21, 22, 23, 24],
[25, 26, 27, 28],
[29, 30, 31, 32]]

the result should be this

C = [[250, 260, 270, 280],
[618, 644, 670, 696],
[986, 1028, 1070, 1112],
[1354, 1412, 1470, 1528]]

i have ran the code multiple times and i get into the problem

    raise ValueError("Matrices must have the same size")
ValueError: Matrices must have the same size
Process finished with exit code 1

if i turn the exception code off i run into a different problem

Traceback (most recent call last):
File "strassen_matrix.py", line 112, in <module>
print(strassen(A, B))
^^^^^^^^^^^^^^
File "strassen_matrix.py", line 97, in strassen
p1 = strassen(matrix_addition(quad1_a, quad4_a), matrix_addition(quad1_b, quad4_b))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "strassen_matrix.py", line 97, in strassen
p1 = strassen(matrix_addition(quad1_a, quad4_a), matrix_addition(quad1_b, quad4_b))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "strassen_matrix.py", line 97, in strassen
p1 = strassen(matrix_addition(quad1_a, quad4_a), matrix_addition(quad1_b, quad4_b))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[Previous line repeated 994 more times]
File "strassen_matrix.py", line 95, in strassen
quad1_a, quad2_a, quad3_a, quad4_a = divide(a)
^^^^^^^^^
File "strassen_matrix.py", line 20, in divide
for x in range(int(len(matrix) / 2)):
^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded while calling a Python objectquer

i tried increasing the recursion limit aswell but still same issue im stumped as to how to fix this any help is appreciated

You have a few errors:

• if len(A) == 1 and len(A[0]) == 1 references the global names A and B instead of the parameter names a and b (also in next statement). Avoid such confusion of names by putting the main logic also in a function, so that its A and B are also local.

• return A[0][0] * B[0][0] returns a number, while the caller expects a matrix. So (together with above fix), it should be

  return [[a[0][0] * b[0][0]]]
  

• In the formula for p2 you have a typo: matrix_addition(quad3_a + quad4_a) should be:

  matrix_addition(quad3_a, quad4_a)
  

• p3 = strassen(quad1_a, matrix_subtraction(quad3_b, quad1_b)) calculates p3 with the opposite sign. You'll want

  p3 = strassen(quad1_a, matrix_subtraction(quad3_b, quad1_b))
  

• final_quad1 = matrix_subtraction(matrix_addition(p1, p4), matrix_addition(p5, p7)) performs a subtraction of two terms instead of just one. Correct to

  final_quad1 = matrix_addition(matrix_subtraction(matrix_addition(p1, p4), p5), p7)
  

After fixing those issues, it will work.