Explicación conceptual del truco de Strassen para la multiplicación de matrices

Question

Los algoritmos de multiplicación rápida de polinomios y números enteros tienen explicaciones conceptuales bien conocidas. Un buen estudio es el de Daniel J. Bernstein Multiplicación rápida de varios dígitos para matemáticos .

Por ejemplo, tanto el truco de Karatsuba como la multiplicación basada en la FFT encajan en el esquema de evaluar e interpolar. Se basan en el hecho de que la evaluación en un punto es un homomorfismo de anillo. El truco de Karatsuba evalúa a bajo coste el producto de dos polinomios lineales en 0, 1 y $\infty$ sin multiplicarlos explícitamente y luego interpola los valores para obtener el producto polinómico. Del mismo modo, la FFT de n puntos evalúa eficazmente un polinomio en las raíces enésimas de la unidad, y la FFT inversa interpola eficazmente un polinomio a partir de sus valores en esos mismos puntos.

También se puede ir más allá de la evaluación y utilizar cualquier homomorfismo de anillo conveniente.

Mi pregunta es si el algoritmo de Strassen para la multiplicación rápida de matrices puede explicarse en términos conceptuales siguiendo estas líneas. El núcleo del algoritmo es El truco de Strassen para calcular productos de matrices 2x2 sobre anillos no conmutativos. Mirando la fórmula de Strassen, es difícil quitarse la sensación de que algunos debería funcionar.

Answer 1

Que yo sepa, la multiplicación rápida de matrices no se basa en homomorfismos de anillos, sino en la noción de rango tensorial . Más concretamente, la forma trilineal $(A,B,C)\mapsto{\rm Tr}(ABC)$ se extiende como una forma lineal $L$ en $$M_{n\times m}\otimes M_{m\times p}\otimes M_{p\times n}.$$

El rango tensorial de $L$ es el número mínimo $r$ en el que puede escribir $$L=\sum_{j=1}^re_j\otimes f_j\otimes g_j,$$ con $e,f,g$ formas lineales. A continuación, el cálculo de $AB$ sólo necesita $r$ multiplicación y un cierto número de sumas. Esto último tiene poca importancia, porque cuando se aplica la fórmula recursivamente a matrices (digamos cuadradas) de tamaño $Nn$ el número de operaciones crece como $r^N$ . Esto se ve fácilmente en el caso $n=2$ donde $r=7$ y la fórmula anterior implica tantos como $16$ adiciones. Para $2^N\times2^N$ matrices, el número de operaciones está limitado por $C7^N=C(2^N)^\alpha$ con $\alpha=\frac{\log7}{\log2}<3$ .

Observe que si sólo tuviera dos espacios (en lugar de $3$ ), entonces el rango tensorial sobre $E\otimes F$ es sólo el rango del álgebra lineal.