Algoritmo de Strassen

En la disciplina matemática del álgebra lineal, el algoritmo de Strassen, llamado así por Volker Strassen, es un algoritmo usado para la multiplicación de matrices.Es asintóticamente más rápido que el algoritmo de multiplicación de matrices estándar, pero más lento que el algoritmo más rápido conocido, y es útil en la práctica para matrices grandes.Sean A, B dos matrices cuadradas sobre un anillo R. Queremos calcular la matriz C como producto Si las matrices A, B no son de tipo 2n x 2n habrá que rellenar lo que falta de filas y columnas con ceros.Todavía tenemos 8 multiplicaciones para calcular la matriz Ci, j , que es el mismo número de multiplicaciones que se necesitan cuando se usa el método estándar de multiplicación de matrices.Definimos las matrices de nuevo que luego se utilizan para expresar Ci, j en términos de Mk.Debido a nuestra definición de la Mk podemos eliminar una multiplicación de matrices y reducir el número de multiplicaciones a 7 (una multiplicación por cada Mk) y expresar Ci, j como Iteramos n-veces el proceso de división hasta que las submatrices degeneran en números (elementos del anillo R).El punto a partir del cual el algoritmo de Strassen es más eficiente depende de la implementación específica y del hardware.Se ha estimado que el algoritmo de Strassen es más rápido para matrices con anchura desde 32 a 128 para implementaciones optimizadas,[1]​ y 60.000 o más para implementaciones básicas.[2]​ La multiplicación de matrices estándar requiere aproximadamente)operaciones aritméticas (sumas y multiplicaciones); la complejidad asintótica esEntonces por aplicación recursiva del algoritmo de Strassen, vemos que,esto es, la complejidad asintótica para multiplicar matrices de tamaño