Multiplicar matrices

ℹ️

Este algoritmo es trivial de entender lo que hace, pero puede ser complejo de entender las submatrices que hay que operar para cada cuadrante

💡

El truco está en coger cualquier posición del cuadrante que queremos saber que submatrices operar, y ver que subcuadrante de la matriz original 1 se operaría con que subcuadrante de la matriz original 2 para calcular el valor en la posición elegida su estubieramos haciendo la operación matricial normal

# Add two matrices
def sumMatrix(m1, m2):
    if len(m1) != len(m2) or len(m1[0]) != len(m2[0]):
        print("The sum is not possible.")
        return None
    
    result = [[0 for _ in range(len(m1[0]))] for _ in range(len(m1))]
    
    for i in range(len(m1)):
        for j in range(len(m1[0])):
            result[i][j] = m1[i][j] + m2[i][j]
            
    return result

# Extract a submatrix from a matrix (i0, j0) is the upper left corner and (i1, j1) is the lower right corner (both inclusive)
def subMatrix(matrix, i0, j0, i1, j1):
    result = [[0 for _ in range(j1-j0+1)] for _ in range(i1-i0+1)]
    
    for i in range(i0, i1+1):
        for j in range(j0, j1+1):
            result[i-i0][j-j0] = matrix[i][j]
            
    return result

# Print a matrix
def printMatrix(matrix):
    for i in range(len(matrix)):
        print(matrix[i])
        
        
        
# Divide and conquer matrix multiplication
def dyvMatrixMult(m1, m2):
    # Base case
    if len(m1) == 1:
        return [[m1[0][0] * m2[0][0]]]
    # Recursive case
    else:
        rows = len(m1)
        cols = len(m1[0])
        
        m1_11 = subMatrix(m1, 0, 0, rows//2-1, cols//2-1)
        m1_12 = subMatrix(m1, 0, cols//2, rows//2-1, cols-1)
        m1_21 = subMatrix(m1, rows//2, 0, rows-1, cols//2-1)
        m1_22 = subMatrix(m1, rows//2, cols//2, rows-1, cols-1)
        
        m2_11 = subMatrix(m2, 0, 0, rows//2-1, cols//2-1)
        m2_12 = subMatrix(m2, 0, cols//2, rows//2-1, cols-1)
        m2_21 = subMatrix(m2, rows//2, 0, rows-1, cols//2-1)
        m2_22 = subMatrix(m2, rows//2, cols//2, rows-1, cols-1)
        
        # Recursive case
        c11 = sumMatrix(dyvMatrixMult(m1_11, m2_11), dyvMatrixMult(m1_12, m2_21))
        c12 = sumMatrix(dyvMatrixMult(m1_11, m2_12), dyvMatrixMult(m1_12, m2_22))
        c21 = sumMatrix(dyvMatrixMult(m1_21, m2_11), dyvMatrixMult(m1_22, m2_21))
        c22 = sumMatrix(dyvMatrixMult(m1_21, m2_12), dyvMatrixMult(m1_22, m2_22))
        
        # Combine the submatrices
        result = [[0 for _ in range(cols)] for _ in range(rows)]
        for i in range(rows//2):
            for j in range(cols//2):
                result[i][j] = c11[i][j]
                result[i][j+cols//2] = c12[i][j]
                result[i+rows//2][j] = c21[i][j]
                result[i+rows//2][j+cols//2] = c22[i][j]
                
        return result
    
    
if __name__ == "__main__":
    MATRIX1 = [
        [8,4,5,3],
        [3,8,4,6],
        [6,1,3,3],
        [7,2,7,5]
    ]
    
    MATRIX2 = [
        [6,2,3,6],
        [2,3,9,5],
        [5,4,6,3],
        [4,5,2,1]
    ]
    
    res = dyvMatrixMult(MATRIX1, MATRIX2)
    printMatrix(res)