Project DelphiTaller de Tensores

Recursión: el ahorro está en el exponente

En cada producto m_r las entradas de A van a la izquierda y las de B a la derecha: la receta nunca supone que xy = yx. Por eso las entradas pueden ser matrices. Corta dos matrices n × n en cuartos, multiplica los cuartos con 7 productos en vez de 8 y aplica la receta otra vez dentro de cada producto.

Tras k niveles, una matriz de lado n = 2ᵏ cuesta 8ᵏ = n³ a la manera escolar y 7ᵏ = n^2.807 con Strassen (log₂ 7 ≈ 2.807):

lado n escolar Strassen ahorro
2 8 7 12.5 %
8 512 343 33.0 %
1024 1 073 741 824 282 475 249 73.7 %

Un bloque ahorrado ahorra un subárbol entero, en cada nivel. Por eso vale la pena buscar menos bloques. Cuenta solo multiplicaciones: las sumas, el tráfico de memoria y el error de redondeo siguen decidiendo si una librería usa un algoritmo rápido.