Me permite descaradamente copia de una respuesta mía a esta pregunta primero.
La idea detrás de Strassen la multiplicación es la misma que la idea detrás de Karatsuba la multiplicación.
En esto, si tenemos dos números y una base $B$ (quizás $10^6$, por ejemplo), y los números están escritos $a = x_0B + x_1$, $b = y_0B + y_1$, y queremos calcular el $ab$, entonces ingenuamente podríamos decir que es
$ab = x_0 y_0 B^2 + (x_0 y_1 + x_1 y_0)B + x_1 y_1 \qquad$ (se requieren 4 multiplicaciones)
Pero podemos ser más ingenioso, como $x_0y_1 + x_1y_0 = (x_0 + x_1)(y_0 + y_1) - x_0y_0 - x_1y_1 $
Así podemos calcular $ab$ conocer $x_0y_0, x_1y_1$$(x_0 + x_1)(y_0 + y_1)$, que utiliza sólo 3 multiplicaciones. Esto es sólo una mancha de la idea, similar a la de muchos otros slick aritmética trucos por ahí que podría ser encontrado por la inspección, y se hizo popular en la década de 1960. (Hay una buena historia detrás de ella - Karatsuba respondió a un reto de Kolmogorov, que culmina con la prueba de Kolmogorov escribiendo un artículo en Karatsuba del nombre).
Para matrices, un puerto directo de Karatsuba no acaba de funcionar. Pero es fácil comprobar que Strassen es cierto (sólo escritura). Pero es muy claro cómo Strassen llegó a través de ellos. Pero cabe mencionar que Strassen estaba trabajando en muchos numérica de los métodos de estilo de las técnicas para mejorar los cálculos de matriz. También debe mencionarse que Strassen tiene un algoritmo mejorado, mejor que esta técnica, utilizando la transformada rápida de fourier así.
Uno se podría preguntar: bien, podemos hacerlo con 7 multiplicaciones. Podemos hacerlo con 6? Strassen multiplicación ha sido de alrededor desde 1969, por lo que seguramente se le conoce? Este fue un problema abierto hasta pocos años atrás, cuando Landsberg mostró que el 7 es el óptimo. Es trivial y un poco lejos para mí, pero su (corregido después de que se publicó) artículo puede ser encontrado en el arXiv.
Uno también puede preguntarse acerca de $3 \times 3$ matrices. Cómo algunas multiplicaciones son necesarios? Ingenuamente, que lleva 27 de multiplicaciones. Pero se puede hacer en 23. (Véase D. Julian Laderman, no conmutativa algoritmo para la multiplicación de 3×3 matrices utilizando el 23 de muliplications, Bull. Amer. De matemáticas. Soc. 82 (1976) 126-128, MR0395320 (52 #16117).) Es que el óptimo? Que el desconocido - todo lo que se sabe es que se tarda al menos 19. (Pero si usted está interesado en ahorro computacional, de 19 da menos ahorros al afirmar que el $2 \times 2$ de los casos).
Así que, en breve, $7$ es óptimo. No es obvio que es óptimo. Fue una idea muy ingeniosa, incluso, para encontrar el $7$.
