“Multiplicación de matrices rápida y eficiente con el método de Strassen en Swift y Objective-C”

!Hola! ¿Alguna vez has sentido frustración por tener que multiplicar matrices manualmente una y otra vez? Déjame presentarte una solución revolucionaria: ¡el método de Strassen!

Como también he estado en esa situación, me propuse investigar más sobre este método y descubrí algo fascinante: a pesar de que el método común de multiplicación de matrices es más sencillo, no siempre es el más eficiente. De hecho, en muchas ocasiones, el método de Strassen puede ser mucho más rápido y eficiente.

Durante mis investigaciones, me llamó la atención que en diversas entrevistas, se preguntaba principalmente sobre el método de Strassen y no sobre el método común. Esto me motivó aún más a profundizar en su historia y en quién lo inventó.

Así que si alguna vez has tenido problemas con la multiplicación de matrices, ¡no te preocupes! El método de Strassen está aquí para ayudarte a resolver tus problemas de manera más eficiente. Y si te interesa conocer más sobre su historia y su creador, ¡sigue leyendo!

La historia detrás del método de multiplicación de matrices de Volker Strassen

En 1969, Volker Strassen, un matemático alemán, cambió el juego de la matemática con su descubrimiento del método de multiplicación de matrices. Su técnica, conocida como “dividir y conquistar”, divide las matrices en submatrices más pequeñas y las multiplica recursivamente para llegar al resultado final. El método de Strassen fue un gran avance en la matemática computacional, y sigue siendo utilizado hoy en día en áreas como la física, la economía y la ingeniería.

Pero, ¿por qué es tan importante este método de multiplicación de matrices? Bueno, para empezar, la multiplicación de matrices tradicional requiere una cantidad cuadrática de multiplicaciones y adiciones, lo que resulta en un alto costo computacional para matrices grandes. En cambio, el método de Strassen utiliza solo siete multiplicaciones y dieciocho sumas o restas para matrices de orden 2^k. Esto reduce significativamente el tiempo de cálculo necesario para multiplicar matrices grandes.

¡Pero espera! Aunque el método de Strassen es impresionante, su uso práctico se ve limitado debido a que solo es más rápido que la multiplicación de matrices tradicional para matrices muy grandes. Además, su implementación puede ser complicada y puede requerir el uso de técnicas avanzadas de programación.

¡No te preocupes! A continuación, te muestro una implementación en Objective-C y Swift para que puedas ver cómo funciona en la práctica.

Primero vamos a revisar el método convencional para multiplicar matrices.

Multiplicar una Matriz cuadrada.

Este método es comúnmente utilizado y tiene una complejidad asintótica de O(n³). En la implementación en Swift, creamos una matriz C que es inicializada con ceros. Luego, utilizamos tres bucles anidados para iterar sobre los elementos de las matrices A y B y realizar la multiplicación de matrices y asignar los valores resultantes a la matriz C.

Implementación en Swift.

public func squareMatrixMultiply(_ A:[[Int]], _ B:[[Int]]) -> [[Int]]{
 var size = A.count
 var C =  Array(repeating: Array(repeating: 0,count: size), count: size)
for i in 0..<size{
for j in 0..<size{
for k in 0..<size{
     C[i][j] = 0
     C[i][j] = A[i][k] * B[k][j]
   }
  }
 }
}

Implementación en Objective-C.

En la implementación en Objective-C, también creamos una nueva matriz que contendrá el resultado de la multiplicación. En este caso, utilizamos dos bucles anidados para iterar sobre los elementos de las matrices A y B y realizar la multiplicación de matrices. Luego, utilizamos un tercer bucle anidado para sumar los productos de cada fila y columna y asignar los valores resultantes a la nueva matriz.

- (NSArray<NSArray<NSNumber *> *> *)squareMatrixMultiply:(NSArray<NSArray<NSNumber *> *> *)a withMatrix:(NSArray<NSArray<NSNumber *> *> *)b
{
    NSInteger size = a.count;
    
    NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:size];
    
    for (NSInteger i = 0; i < size; i++) {
        
        NSMutableArray *row = [NSMutableArray arrayWithCapacity:size];
        
        for (NSInteger j = 0; j < size; j++) {
            
            NSInteger sum = 0;
            
            for (NSInteger k = 0; k < size; k++) {
                
                sum += [a[i][k] intValue] * [b[k][j] intValue];
            }
            
            [row addObject:@(sum)];
        }
        [newArray addObject:row];
    }
    return newArray;
}

Nota

Se pude definir la antigua funcion de dos maneras:

- (NSArray<NSArray<NSNumber *> *> *)squareMatrixMultiply:(NSArray<NSArray<NSNumber *> *> *)a withMatrix:(NSArray<NSArray<NSNumber *> *> *)b

y

- (NSArray *)squareMatrixMultiply:(NSArray *)a withMatrix:(NSArray *)b

Ambos métodos hacen lo mismo: multiplicar dos matrices cuadradas. Pero difieren en cómo se definen los tipos de argumentos y el valor de retorno.

El primer método utiliza una sintaxis de tipo genérico y se define como una matriz de matrices de objetos NSNumber. Esto lo hace más seguro y fácil de leer, ya que el tipo de elementos que se manejan se especifica de antemano. La ventaja de este enfoque es que el compilador puede verificar el tipo de argumentos y el valor de retorno, lo que ayuda a detectar errores de tipo durante la compilación.

El segundo método utiliza la antigua sintaxis de Objective-C y se define como una matriz de objetos genéricos. En este caso, el método no especifica el tipo de elementos que se manejan de antemano, lo que lo hace menos seguro y más difícil de leer. Sin embargo, se puede usar en proyectos más antiguos que aún no se han actualizado para utilizar la nueva sintaxis.

En resumen, el método definido con sintaxis de tipo genérico es más seguro y fácil de leer, mientras que el método definido con la antigua sintaxis es más compatible con versiones antiguas de Objective-C.

Este método es eficiente, pero su complejidad asintótica es de O(n³), lo que puede ser un problema para matrices muy grandes. Sin embargo, existen otros métodos más eficientes para multiplicar matrices, como el algoritmo de Strassen, que tiene una complejidad asintótica de O(n².⁸³). ¡No te preocupes, lo veremos más adelante!

Antes de continuar, hablemos sobre la manera recursiva del método squareMatrixMultiply. Esto implica que la función se llama a sí misma varias veces para multiplicar las submatrices de las matrices originales.

Multiplicar una Matriz cuadrada de manera Recursiva.

La multiplicación de matrices recursiva divide la multiplicación de la matriz en subproblemas más pequeños, lo que reduce la cantidad de operaciones necesarias. Esta técnica puede ser muy eficiente para matrices grandes, pero puede ser más difícil de implementar y puede requerir más memoria debido a la naturaleza recursiva del algoritmo.

¡Echemos un vistazo al código!

Implementación en Swift.

public func squareMatrixMultiplyRecursive(_ a: [[Int]], _ b: [[Int]] ) -> [[Int]] {
    
    var lenght = a.count
    
    var newArray = Array(repeating: Array(repeating: 0, count: lenght), count: lenght)
    
    guard lenght > 1 else {
            return [[a[0][0] * b[0][0]]]
        }
    
    let halfArray = lenght / 2
    var a11 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var a12 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var a21 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var a22 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var b11 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var b12 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var b21 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var b22 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    
    for i in 0..<halfArray {
        for j in 0..<halfArray {
            
            a11[i][j] = a[i][j]
            a12[i][j] = a[i][j+halfArray]
            a21[i][j] = a[i+halfArray][j]
            a22[i][j] = a[i+halfArray][j+halfArray]
            
            b11[i][j] = b[i][j]
            b12[i][j] = b[i][j+halfArray]
            b21[i][j] = b[i+halfArray][j]
            b22[i][j] = b[i+halfArray][j+halfArray]
        }
    }
    
    // Compute the four products recursively
    let c11 = squareMatrixAddition(squareMatrixMultiplyRecursive(a11, b11), squareMatrixMultiplyRecursive(a12, b21))
        let c12 = squareMatrixAddition(squareMatrixMultiplyRecursive(a11, b12), squareMatrixMultiplyRecursive(a12, b22))
        let c21 = squareMatrixAddition(squareMatrixMultiplyRecursive(a21, b11), squareMatrixMultiplyRecursive(a22, b21))
        let c22 = squareMatrixAddition(squareMatrixMultiplyRecursive(a21, b12), squareMatrixMultiplyRecursive(a22, b22))
        
    // Combine the four submatrices into the result
    for i in 0..<halfArray {
        for j in 0..<halfArray {
            newArray[i][j] = c11[i][j]
            newArray[i][j+halfArray] = c12[i][j]
            newArray[i+halfArray][j] = c21[i][j]
            newArray[i+halfArray][j+halfArray] = c22[i][j]
        }
    }
    
    return newArray
}

private func squareMatrixAddition( _ a: [[Int]], _ b: [[Int]] ) -> [[Int]] {
    var lenght = a.count
    var newArray = Array(Array(repeating: Array(Array(repeating: 0, count: lenght)), count: lenght))
    
    for i in 0..<lenght{
        for j in 0..<lenght{
            newArray[i][j] = a[i][j] + b[i][j]
        }
    }
    return newArray
}

Implementación en Objective-C.

- (NSArray *)squareMatrixMultiplyRecursive:(NSArray *)a withMatrix:(NSArray *)b
{
    if (a.count != b.count) {
            NSLog(@"Error: Las matrices deben tener el mismo tamaño");
            return nil;
    }
    NSInteger size = a.count;
    
    NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:size];
    
    for (NSInteger i = 0; i < size; i++)
    {
        NSMutableArray *row = [NSMutableArray arrayWithCapacity:size];
        
        for(NSInteger j = 0; j < size; j++)
        {
            [row addObject:@(0)];
        }
        [newArray addObject:row];
    }
    
    if (size <= 1)
    {
    return @[ @[ @( [a[0][0] intValue] * [b[0][0] intValue]) ] ];
    }
    
    NSInteger halfArray = size / 2;
    NSMutableArray *a11 = [NSMutableArray arrayWithCapacity:halfArray];
    NSMutableArray *a12 = [NSMutableArray arrayWithCapacity:halfArray];
    NSMutableArray *a21 = [NSMutableArray arrayWithCapacity:halfArray];
    NSMutableArray *a22 = [NSMutableArray arrayWithCapacity:halfArray];
    NSMutableArray *b11 = [NSMutableArray arrayWithCapacity:halfArray];
    NSMutableArray *b12 = [NSMutableArray arrayWithCapacity:halfArray];
    NSMutableArray *b21 = [NSMutableArray arrayWithCapacity:halfArray];
    NSMutableArray *b22 = [NSMutableArray arrayWithCapacity:halfArray];
    
    for (NSInteger i = 0; i < halfArray; i++)
    {
        [a11 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
        [a12 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
        [a21 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
        [a22 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
        [b11 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
        [b12 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
        [b21 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
        [b22 addObject:[NSMutableArray arrayWithCapacity:halfArray]];
    }

    for (NSInteger i = 0; i < halfArray; i++) {
        for (NSInteger j = 0; j < halfArray; j++) {
            a11[i][j] = a[i][j];
            a12[i][j] = a[i][j+halfArray];
            a21[i][j] = a[i+halfArray][j];
            a22[i][j] = a[i+halfArray][j+halfArray];
            b11[i][j] = b[i][j];
            b12[i][j] = b[i][j+halfArray];
            b21[i][j] = b[i+halfArray][j];
            b22[i][j] = b[i+halfArray][j+halfArray];
        }
    }
    
    NSArray *C11 = [self squareMatrixAddition:[self squareMatrixMultiplyRecursive:a11 withMatrix:b11] withMatrix:[self squareMatrixMultiplyRecursive:a12 withMatrix:b21]];
    NSArray *C12 = [self squareMatrixAddition:[self squareMatrixMultiplyRecursive:a11 withMatrix:b12] withMatrix:[self squareMatrixMultiplyRecursive:a12 withMatrix:b22]];
    NSArray *C21 = [self squareMatrixAddition:[self squareMatrixMultiplyRecursive:a21 withMatrix:b11] withMatrix:[self squareMatrixMultiplyRecursive:a22 withMatrix:b22]];
    
    NSArray *C22 = [self squareMatrixAddition:[self squareMatrixMultiplyRecursive:a21 withMatrix:b12] withMatrix:[self squareMatrixMultiplyRecursive:a22 withMatrix:b22]];


   for (NSInteger i = 0; i < halfArray; i++) {
       for (NSInteger j = 0; j < halfArray; j++) {
           newArray[i][j] = C11[i][j];
           newArray[i][j+halfArray] = C12[i][j];
           newArray[i+halfArray][j] = C21[i][j];
           newArray[i+halfArray][j+halfArray] = C22[i][j];
        }
    }

    return newArray;
    
}

- (NSArray *)squareMatrixAddition:(NSArray*)a withMatrix:(NSArray*)b{
    
    NSInteger size = [a count];
    NSMutableArray * newArray = [NSMutableArray arrayWithCapacity:size];
    
    for (NSInteger i = 0; i < size; i++) {
        NSMutableArray *row = [NSMutableArray arrayWithCapacity:size];
        
        for (NSInteger j = 0; j < size ; j++){
            row[j] = @([a[i][j] integerValue] + [b[i][j] integerValue]);
        }
        [newArray addObject:row];
    }
    
    return newArray;
}

Al ver ambos códigos, podemos notar que se creó un predecesor al método de Strassen al querer hacer recursiva nuestra función de multiplicación de matrices cuadradas.

¡Ojo! Al utilizar este método, podemos reducir la complejidad del algoritmo de multiplicación de matrices de O(n³) a O(n^(log2(7))) en promedio. Además, ¡fíjate! el método de Strassen es utilizado en diversas áreas, como la criptografía y el procesamiento de señales. ¡Así que, cachay! se puede apreciar la importancia de conocer y entender este método en el campo de la computación.

¡Ahora vamos a echar un vistazo al famoso método de Strassen.!

Algoritmo Strassen.

Ahora vamos a explorar el algoritmo de Strassen. El concepto principal es dividir las matrices A y B en ocho submatrices, luego calcular recursivamente las submatrices de C. Este enfoque es conocido como dividir y conquistar!.

Las siguientes son las ocho llamadas recursivas involucradas:

• a * e
• b * g
• a * f
• b * h
• c * e
• d * g
• c * f
• d * h

Estas ocho llamadas recursivas se combinan para formar los cuatro cuadrantes de C.

Aunque este paso por sí solo no mejora la complejidad, Strassen se dio cuenta de que no necesitas las ocho llamadas recursivas para completar el proceso. Con algunas sumas y restas, puedes terminar la operación con solo siete llamadas recursivas. Usando el Teorema Maestro con T(n) = 8T(n/2) + O(n²), la complejidad temporal sigue siendo O(n³), ¡Vaya que complicado teorema!.

De esta manera quedarían al final las 7 funciones que strassen propone.

• a * (f — h)

• (a + b) * h

• (c + d) * e

• d * (g — e)

• (a + d) * (e + h)

• (b — d) * (g + h)

• (a — c) * (e + f)

Finalmente, cada submatriz del método Strassen sigue un patrón similar. Después de leer la implementación del algoritmo de los amigos de Kodeco (antes RayWenderlich), me confundió un poco. Así que decidí hacerlo de una manera más fácil de entender. Aquí está el enlace a su explicación si quieres saber más: https://www.kodeco.com/5740-swift-algorithm-club-strassen-s-algorithm.

La matriz final quedaría así. Una vez que tenemos nuestras 7 submatrices, podemos empezar a agruparlas para obtener los resultados de cada cuadrante de la matriz final.

Matriz C = |C11 = p5+p4-p2+p6. |  C21 = p1+p2        |

           |C12 = p3+p4.       |  C22 = p1+p5-p3-p7. |

Para explicar la primera matriz más pequeña, podemos simplificarla de la siguiente manera:

C11 = p5+p4-p2+p6 = (a+d)*(e+h) + d*(g-e) - (a+b)*h + (b-d)*(g+h)
            = (ae+de+ah+dh) + (dg-de) - (ah+bh) + (bg-dg+bh-dh)
            = ae+bg ✅

Nuestra segunda matriz más pequeña es:

C21 = p1+p2 = a*(f-h) + (a+b)*h
 = (af-ah) + (ah+bh)
 = af+bh ✅

Para nuestra tercera matriz más pequeña:

 C12 = p3+p4 = (c+d)*e + d*(g-e)
      = (ce+de) + (dg-de)
      = ce+dg ✅

Y por último, nuestra cuarta matriz no tan pequeña:

C22 = p1+p5-p3-p7 = a*(f-h) + (a+d)*(e+h) - (c+d)*e - (a-c)*(e+f)
            = (af-ah) + (ae+de+ah+dh) -(ce+de) - (ae-ce+af-cf)
            = cf+dh ✅

Supongamos que tienes una matriz A de tamaño 3×2 y necesitas dividirla. ¿Debería el renglón del medio incluirse en la división superior o inferior? Lamentablemente, no es posible dividir esta matriz de manera uniforme, por lo que este caso especial debe manejarse explícitamente. Aunque esto puede parecer un desafío, si aumentas el tamaño de la matriz hasta que se convierta en una matriz cuadrada con filas y columnas que sean potencia de dos y par, puedes asegurarte de que el caso especial nunca surja. Además, dado que el trabajo de preparación solo introduce filas y columnas de ceros, el resultado permanece sin cambios.

Para este caso, simplemente debes verificar si la matriz A es más grande que la matriz B, y agregar los 0 donde deban ir solo si A es más grande que B. Sería un gran desafío hacer que funcione para ambos casos (aunque el método Strassen solo funciona para matrices pequeñas, una matriz más grande tendría que usar un algoritmo diferente) que también tendría que ser verificado adecuadamente ya que la matriz B nunca puede ser más grande que A. ¡Sería genial si alguien pudiera comentar sobre esto!

Implementación en Swift

public func strassensMethodImplementation(_ A:[[Int]] ,_ B:[[Int]]) -> [[Int]]{
    
    let lenght = A.count
    var newArray = Array(repeating: Array(Array(repeating: 0, count: lenght)), count: lenght)
    
    guard lenght > 1 else{
          return [[A[0][0] * B[0][0]]]
      }
    let halfArray = lenght/2
    let isOdd = lenght % 2 == 1
    var A11 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var A12 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var A21 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var A22 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    
    var B11 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var B12 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var B21 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    var B22 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    
    for i in 0..<halfArray{
        for j in 0..<halfArray{
            A11[i][j] = A[i][j]
            A12[i][j] = A[i][j+halfArray]
            A21[i][j] = A[i+halfArray][j]
            A22[i][j] = A[i+halfArray][j+halfArray]
            
            B11[i][j] = B[i][j]
            B12[i][j] = B[i][j+halfArray]
            B21[i][j] = B[i+halfArray][j]
            B22[i][j] = B[i+halfArray][j+halfArray]
        }
    }
    
    var C11: [[Int]] =  [[Int]]()
    var C12: [[Int]] =  [[Int]]()
    var C21: [[Int]] =  [[Int]]()
    var C22: [[Int]] =  [[Int]]()
    
    if isOdd {
        C11 = Array(repeating: Array(repeating: 0, count: halfArray + 1), count: halfArray + 1)
        C12 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray + 1)
        C21 = Array(repeating: Array(repeating: 0, count: halfArray + 1), count: halfArray)
        C22 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray + 1)
    }else {
        C11 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
        C12 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
        C21 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
        C22 = Array(repeating: Array(repeating: 0, count: halfArray), count: halfArray)
    }
    
    let p1 = strassensMethodImplementation(auxiliarSubstraction(B12, B22),A11)
    let p2 = strassensMethodImplementation(auxiliarSumatory(A11, A12), B22)
    let p3 = strassensMethodImplementation(auxiliarSumatory(A21, A22), B11)
    let p4 = strassensMethodImplementation(A22, auxiliarSubstraction(B21, B11))
    let p5 = strassensMethodImplementation(auxiliarSumatory(A11, A22), auxiliarSumatory(B11, B22))
    let p6 = strassensMethodImplementation(auxiliarSubstraction(A12, A22),  auxiliarSumatory(B21, B22))
    let p7 = strassensMethodImplementation(auxiliarSubstraction(A11, A21), auxiliarSumatory(B11, B12))
    
    let C11Sum = auxiliarSumatory(auxiliarSubstraction(auxiliarSumatory(p5, p4), p2), p6)
    let C12Sum = auxiliarSumatory(p1, p2)
    let C21Sum = auxiliarSumatory(p3, p4)
    let C22Sum = auxiliarSubstraction(auxiliarSubstraction(auxiliarSumatory(p5, p1), p3), p7)
    
    for i in 0..<halfArray {
        for j in 0..<halfArray {
            newArray[i][j] = C11Sum[i][j]
            newArray[i][j+halfArray] = C12Sum[i][j]
            newArray[i+halfArray][j] = C21Sum[i][j]
            newArray[i+halfArray][j+halfArray] = C22Sum[i][j]
        }
    }
    
    return newArray
}

private func auxiliarSumatory(_ A:[[Int]],_ B:[[Int]]) ->[[Int]] {
    let lenght = A.count
    var newArray = Array(repeating: Array(repeating: 0, count: lenght), count: lenght)
    
    for i in 0..<lenght{
        for j in 0..<lenght{
            newArray[i][j] = A[i][j] + B[i][j]
        }
    }
    return newArray
}

private func auxiliarSubstraction(_ A:[[Int]],_ B:[[Int]]) -> [[Int]]{
    let lenght = A.count
    var newArray = Array(repeating: Array(repeating: 0, count: lenght), count: lenght)
    
    for i in 0..<lenght{
        for j in 0..<lenght{
            newArray[i][j] = A[i][j] - B[i][j]
        }
    }
    return newArray
}

Implementación en Objective-C.

- (NSArray * )strassenMethod:(NSArray * )a withMatrix:(NSArray *)b
{
    
    NSInteger size = [a count];;
    NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:size];
    
    for (NSInteger i = 0 ; i <  size ; i ++) {
        NSMutableArray *row = [NSMutableArray arrayWithCapacity:size];
        for (NSInteger j = 0 ; j < size ; j++){
            [row addObject:@(0)];
        }
        [newArray addObject:row];
    }
    if (size == 1) {
        return @[@[@( [a[0][0]integerValue] * [b[0][0]integerValue]) ]];
    }
    
    
    NSInteger halfSize = size/2;
    BOOL isOdd = size%2 == 1;
    
    NSMutableArray *a11 = [NSMutableArray arrayWithCapacity:halfSize];
    NSMutableArray *a12 = [NSMutableArray arrayWithCapacity:halfSize];
    NSMutableArray *a21 = [NSMutableArray arrayWithCapacity:halfSize];
    NSMutableArray *a22 = [NSMutableArray arrayWithCapacity:halfSize];
    
    NSMutableArray *b11 = [NSMutableArray arrayWithCapacity:halfSize];
    NSMutableArray *b12 = [NSMutableArray arrayWithCapacity:halfSize];
    NSMutableArray *b21 = [NSMutableArray arrayWithCapacity:halfSize];
    NSMutableArray *b22 = [NSMutableArray arrayWithCapacity:halfSize];
    
    for (NSInteger i = 0 ; i < halfSize ; i++)
    {
        [a11 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        [a12 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        [a21 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        [a22 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        [b11 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        [b12 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        [b21 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        [b22 addObject:[NSMutableArray arrayWithCapacity:halfSize]];
        
    }
    
    for (NSInteger i = 0; i < halfSize; i++) {
        for (NSInteger j = 0; j < halfSize; j++) {
            a11[i][j] = a[i][j];
            a12[i][j] = a[i][j+halfSize];
            a21[i][j] = a[i+halfSize][j];
            a22[i][j] = a[i+halfSize][j+halfSize];
            b11[i][j] = b[i][j];
            b12[i][j] = b[i][j+halfSize];
            b21[i][j] = b[i+halfSize][j];
            b22[i][j] = b[i+halfSize][j+halfSize];
        }
    }
    
    NSMutableArray *C11,*C12,*C21,*C22;
    
    if (isOdd) {
        C11 = [NSMutableArray arrayWithCapacity:halfSize+1];
        C12 = [NSMutableArray arrayWithCapacity:halfSize+1];
        C21 = [NSMutableArray arrayWithCapacity:halfSize];
        C22 = [NSMutableArray arrayWithCapacity:halfSize+1];
        for (int i = 0; i < halfSize+1; i++) {
            NSMutableArray *innerArray11 = [NSMutableArray arrayWithCapacity:halfSize+1];
            NSMutableArray *innerArray12 = [NSMutableArray arrayWithCapacity:halfSize];
            NSMutableArray *innerArray21 = [NSMutableArray arrayWithCapacity:halfSize+1];
            NSMutableArray *innerArray22 = [NSMutableArray arrayWithCapacity:halfSize];
            for (int j = 0; j < halfSize+1; j++) {
                [innerArray11 addObject:@(0)];
                [innerArray12 addObject:@(0)];
                [innerArray21 addObject:@(0)];
                [innerArray22 addObject:@(0)];
            }
            [C11 addObject:innerArray11];
            [C12 addObject:innerArray12];
            [C21 addObject:innerArray21];
            [C22 addObject:innerArray22];
        }
    } else {
        C11 = [NSMutableArray arrayWithCapacity:halfSize];
        C12 = [NSMutableArray arrayWithCapacity:halfSize];
        C21 = [NSMutableArray arrayWithCapacity:halfSize];
        C22 = [NSMutableArray arrayWithCapacity:halfSize];
        for (int i = 0; i < halfSize; i++) {
            NSMutableArray *innerArray11 = [NSMutableArray arrayWithCapacity:halfSize];
            NSMutableArray *innerArray12 = [NSMutableArray arrayWithCapacity:halfSize];
            NSMutableArray *innerArray21 = [NSMutableArray arrayWithCapacity:halfSize];
            NSMutableArray *innerArray22 = [NSMutableArray arrayWithCapacity:halfSize];
            for (int j = 0; j < halfSize; j++) {
                [innerArray11 addObject:@(0)];
                [innerArray12 addObject:@(0)];
                [innerArray21 addObject:@(0)];
                [innerArray22 addObject:@(0)];
            }
            [C11 addObject:innerArray11];
            [C12 addObject:innerArray12];
            [C21 addObject:innerArray21];
            [C22 addObject:innerArray22];
        }
    }
    
    NSMutableArray *p1, *p2, *p3, *p4, *p5, *p6, *p7, *C11Sum, *C12Sum, *C21Sum, *C22Sum;

    p1 = [self strassenMethod: [self squareMatrixSubstraction: b12 withMatrix:b22] withMatrix:a11];
    p2 = [self strassenMethod: [self squareMatrixAddition: a11 withMatrix:a12] withMatrix:b22];
    p3 = [self strassenMethod: [self squareMatrixAddition: a21 withMatrix:a22] withMatrix:b11];
    p4 = [self strassenMethod: a22 withMatrix:[self squareMatrixSubstraction: b21 withMatrix:b11]];
    p5 = [self strassenMethod: [self squareMatrixAddition: a11 withMatrix:a22] withMatrix:[self squareMatrixAddition: b11 withMatrix:b22]];
    p6 = [self strassenMethod: [self squareMatrixSubstraction: a12 withMatrix:a22] withMatrix:[self squareMatrixAddition: b21 withMatrix:b22]];
    p7 = [self strassenMethod: [self squareMatrixSubstraction: a11 withMatrix:a21] withMatrix:[self squareMatrixAddition: b11 withMatrix:b12]];

    C11Sum = [self squareMatrixAddition: [self squareMatrixSubstraction: [self squareMatrixAddition: p5 withMatrix:p4] withMatrix:p2] withMatrix:p6];
    C12Sum = [self squareMatrixAddition: p1 withMatrix:p2];
    C21Sum = [self squareMatrixAddition: p3 withMatrix:p4];
    C22Sum = [self squareMatrixSubstraction: [self squareMatrixSubstraction: [self squareMatrixAddition: p5 withMatrix:p1] withMatrix:p3] withMatrix:p7];

    for (int i = 0; i < halfSize; i++) {
        for (int j = 0; j < halfSize; j++) {
           newArray[i][j] = C11Sum[i][j];
           newArray[i][j+halfSize] = C12Sum[i][j];
           newArray[i+halfSize][j] = C21Sum[i][j];
           newArray[i+halfSize][j+halfSize] = C22Sum[i][j];
            
        }
    }
      return newArray;
}

// MARK: Private functions
- (NSArray *)squareMatrixAddition:(NSArray*)a withMatrix:(NSArray*)b{
    
    NSInteger size = [a count];
    NSMutableArray * newArray = [NSMutableArray arrayWithCapacity:size];
    
    for (NSInteger i = 0; i < size; i++) {
        NSMutableArray *row = [NSMutableArray arrayWithCapacity:size];
        
        for (NSInteger j = 0; j < size ; j++){
            row[j] = @([a[i][j] integerValue] + [b[i][j] integerValue]);
        }
        [newArray addObject:row];
    }
    
    return newArray;
}

- (NSArray *)squareMatrixSubstraction:(NSArray *)a withMatrix:(NSArray*)b
{
    NSInteger size = [a count];
    NSMutableArray *newArray = [NSMutableArray arrayWithCapacity:size];
    
    for (NSInteger i = 0 ; i < size ; i++) {
        NSMutableArray *row = [NSMutableArray arrayWithCapacity:size];
        for (NSInteger j = 0 ; j < size ; j++) {
            row[j] = @([a[i][j] integerValue] - [b[i][j]integerValue]);
        }
        [newArray addObject:(row)];
    }
    return newArray;
}

Nota: Si introduce una matriz A más grande que B, no se obtendrán los resultados correctos. En su lugar, se añadirán unos cuantos ceros para completar la matriz. Si se desea el resultado correcto de una multiplicación de una matriz de 3x2, se deben seguir unos pasos adicionales para cuidar los valores de a31, a32 y a33. Lo mismo sucede si se quiere una multiplicación diferente a 2x2.😅

Por supuesto, no nos iremos sin antes mostrar las pruebas unitarias. Es probable que el código tenga algunos errores o le falte implementación, pero creo que es mucho más comprensible que el ejemplo expuesto por Kodeco o Raywenderlich. Además, es más fácil de seguir si lo lees línea por línea en lugar de tener que revisar los métodos ya declarados por ellos. Pero sin más preámbulos, aquí te dejo las pruebas unitarias.

-(void)test_StrasenMethod2x2
{
    NSArray<NSArray<NSNumber *> *> *a =  @[ @[@1, @2], @[@3, @4]  ];;
    NSArray<NSArray<NSNumber *> *> *b = @[ @[@5, @6], @[@7, @8] ];
    NSArray<NSArray<NSNumber *> *> *expectedResult = @[ @[@19, @22 ] , @[@43, @50] ];
    NSArray<NSArray<NSNumber *>*> *ownStrassen = [squareAlgorithm strassenMethod:a withMatrix:b];
    XCTAssertEqualObjects(ownStrassen,expectedResult);
    
}

-(void)test_StrasenMethod3x2
{
    NSArray<NSArray<NSNumber *> *> *a =  @[ @[@1, @2], @[@3, @4], @[@9, @10] ];;
    NSArray<NSArray<NSNumber *> *> *b = @[ @[@5, @6], @[@7, @8] ];
    NSArray<NSArray<NSNumber *> *> *expectedResult = @[ @[@19, @22, @0] , @[@43, @50, @0] ,  @[@0, @0, @0] ];
    NSArray<NSArray<NSNumber *>*> *ownStrassen = [squareAlgorithm strassenMethod:a withMatrix:b];
    XCTAssertEqualObjects(ownStrassen,expectedResult);
}

 func test_StrasenMethod2x2() 
{
   let a = [[1, 2], [3, 4]]
   let b = [[5, 6], [7, 8]]
   let expectedResult  = [[19, 22], [43, 50]]
   let ownStrassen = squareAlgorithm.strassenMethod(a, withMatrix: b)

     XCTAssertEqual(ownStrassen, expectedResult)
}

func test_StrasenMethod3x2() 
{
    let a = [[1, 2], [3, 4], [9, 10]]
    let b = [[5, 6], [7, 8]]
    let expectedResult  = [[19, 22, 0], [43, 50, 0], [0, 0, 0]]
    let ownStrassen = squareAlgorithm.strassenMethod(a, withMatrix: b)

   XCTAssertEqual(ownStrassen, expectedResult)
}

Espero que mi explicación haya sido de ayuda y que hayan comprendido todo. Si tienen algún comentario o sugerencia, por favor háganmelo saber en la sección de comentarios y estaré encantado de corregirlo. Espero que les sea útil en alguna situación y contribuya a mejorar su experiencia como desarrolladores. Gracias.!