Algoritmo de Strassen

En álgebra lineal , el algoritmo de Strassen , que lleva el nombre de Volker Strassen , es un algoritmo para la multiplicación de matrices . Es más rápido que el algoritmo estándar de multiplicación de matrices para matrices grandes, con una mejor complejidad asintótica (${\displaystyle O(n^{\log _{2}7})}$versus${\displaystyle O(n^{3})}$), aunque el algoritmo ingenuo suele ser mejor para matrices pequeñas. El algoritmo de Strassen es más lento que los algoritmos más rápidos conocidos para matrices extremadamente grandes, pero estos algoritmos galácticos no son útiles en la práctica, ya que son mucho más lentos para matrices de tamaño práctico. Para matrices pequeñas existen algoritmos aún más rápidos.

El algoritmo de Strassen funciona para cualquier anillo , como plus/multiply, pero no para todos los semianillos , como min-plus o el álgebra booleana , donde el algoritmo ingenuo todavía funciona, y la llamada multiplicación combinatoria de matrices .

Volker Strassen publicó por primera vez este algoritmo en 1969 y, por lo tanto, demostró que el${\displaystyle n^{3}}$El algoritmo general de multiplicación de matrices no era óptimo. ^{[ 1 ]} La publicación del algoritmo de Strassen dio lugar a más investigaciones sobre la multiplicación de matrices que condujeron tanto a cotas inferiores asintóticas como a cotas superiores computacionales mejoradas.

Dejar${\displaystyle A}$,${\displaystyle B}$sean dos matrices cuadradas sobre un anillo${\displaystyle {\mathcal {R}}}$Por ejemplo, matrices cuyas entradas son números enteros o números reales. El objetivo de la multiplicación de matrices es calcular el producto de la matriz.${\displaystyle C=AB}$. La siguiente exposición del algoritmo supone que todas estas matrices tienen tamaños que son potencias de dos (es decir,${\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}$), pero esto solo es conceptualmente necesario, si las matrices${\displaystyle A}$,${\displaystyle B}$no son de tipo${\displaystyle 2^{n}\times 2^{n}}$Las filas y columnas "faltantes" se pueden rellenar con ceros para obtener matrices con tamaños que son potencias de dos, aunque las implementaciones reales del algoritmo no hacen esto en la práctica.

Las particiones del algoritmo de Strassen${\displaystyle A}$,${\displaystyle B}$y${\displaystyle C}$en matrices de bloques de igual tamaño

${\displaystyle A={\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}},\quad C={\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}},\quad }$

con${\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})}$El algoritmo ingenuo sería:

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.}$

Esta construcción no reduce el número de multiplicaciones: todavía se necesitan 8 multiplicaciones de bloques de matriz para calcular el${\displaystyle C_{ij}}$matrices, el mismo número de multiplicaciones necesarias que cuando se utiliza la multiplicación de matrices estándar.

El algoritmo de Strassen define nuevos valores:

${\displaystyle {\begin{aligned}M_{1}&=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\\M_{2}&=(A_{21}+A_{22}){\color {red}\times }B_{11};\\M_{3}&=A_{11}{\color {red}\times }(B_{12}-B_{22});\\M_{4}&=A_{22}{\color {red}\times }(B_{21}-B_{11});\\M_{5}&=(A_{11}+A_{12}){\color {red}\times }B_{22};\\M_{6}&=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\\M_{7}&=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\\end{aligned}}}$

utilizando solo 7 multiplicaciones (una por cada${\displaystyle M_{k}}$) en lugar de 8. Ahora podemos expresar el${\displaystyle C_{ij}}$en términos de${\displaystyle M_{k}}$:

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &M_{3}+M_{5}\\M_{2}+M_{4}\quad &M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.}$

Iteramos recursivamente este proceso de división hasta que las submatrices degeneran en números (elementos del anillo).${\displaystyle {\mathcal {R}}}$). Si, como se mencionó anteriormente, la matriz original tenía un tamaño que no era una potencia de 2, entonces el producto resultante tendrá filas y columnas cero, al igual que${\displaystyle A}$y${\displaystyle B}$y estos serán eliminados en este punto para obtener la matriz (más pequeña)${\displaystyle C}$Realmente lo queríamos.

Las implementaciones prácticas del algoritmo de Strassen cambian a métodos estándar de multiplicación de matrices para submatrices suficientemente pequeñas, para las cuales esos algoritmos son más eficientes. El punto de cruce particular para el cual el algoritmo de Strassen es más eficiente depende de la implementación y el hardware específicos. Autores anteriores habían estimado que el algoritmo de Strassen es más rápido para matrices con anchos de 32 a 128 para implementaciones optimizadas. ^{[ 2 ]} Sin embargo, se ha observado que este punto de cruce ha ido aumentando en los últimos años, y un estudio de 2010 encontró que incluso un solo paso del algoritmo de Strassen a menudo no es beneficioso en las arquitecturas actuales, en comparación con una multiplicación tradicional altamente optimizada, hasta que los tamaños de matriz superan los 1000 o más, e incluso para tamaños de matriz de varios miles el beneficio suele ser marginal en el mejor de los casos (alrededor del 10% o menos). ^{[ 3 ]} Un estudio más reciente (2016) observó beneficios para matrices tan pequeñas como 512 y un beneficio de alrededor del 20%. ^{[ 4 ]}

Es posible reducir el número de sumas de matrices utilizando en su lugar la siguiente forma descubierta por Winograd en 1971: ^{[ 5 ]}

${\displaystyle {\begin{bmatrix}a&b\\c&d\end{bmatrix}}{\begin{bmatrix}A&C\\B&D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&w+v+(a+bcd){\color {red}\times }D\\w+u+d{\color {red}\times }(B+CAD)&w+u+v\end{bmatrix}}}$

dónde${\displaystyle t=a{\color {red}\times }A,\;u=(ca){\color {red}\times }(CD),\;v=(c+d){\color {red}\times }(CA),\;w=t+(c+da){\color {red}\times }(A+DC)}$.

Esto reduce el número de sumas y restas de matrices de 18 a 15. El número de multiplicaciones de matrices sigue siendo 7, y la complejidad asintótica es la misma. ^{[ 6 ]}

El algoritmo se optimizó aún más en 2017 utilizando una base alternativa, ^{[ 7 ]} reduciendo el número de sumas de matrices por paso bilineal a 12 mientras se mantiene el número de multiplicaciones de matrices, y de nuevo en 2023: ^{[ 8 ]}

${\displaystyle {\begin{aligned}A_{22}&=A_{12}-A_{21}+A_{22};\\B_{22}&=B_{12}-B_{21}+B_{22},\end{aligned}}}$

${\displaystyle {\begin{aligned}C_{12}&=C_{12}-C_{22};\\C_{21}&=C_{22}-C_{21},\end{aligned}}}$

El esquema del algoritmo anterior mostró que se puede prescindir de las 7 multiplicaciones de matrices tradicionales para los subbloques de la matriz, en lugar de las 8. Por otro lado, es necesario realizar sumas y restas de bloques, aunque esto no afecta la complejidad general: Sumar matrices de tamaño${\displaystyle N/2}$requiere solo${\displaystyle (N/2)^{2}}$operaciones mientras que la multiplicación es sustancialmente más costosa (tradicionalmente${\displaystyle 2(N/2)^{3}}$operaciones de suma o multiplicación).

La pregunta entonces es cuántas operaciones se necesitan exactamente para los algoritmos de Strassen, y cómo se compara esto con la multiplicación de matrices estándar que toma aproximadamente${\displaystyle 2N^{3}}$(dónde${\displaystyle N=2^{n}}$operaciones aritméticas, es decir, una complejidad asintótica${\displaystyle \Theta (N^{3})}$.

El número de sumas y multiplicaciones requeridas en el algoritmo de Strassen se puede calcular de la siguiente manera: sea${\displaystyle f(n)}$sea ​​el número de operaciones para una${\displaystyle 2^{n}\times 2^{n}}$matriz. Luego, mediante la aplicación recursiva del algoritmo de Strassen, vemos que${\displaystyle f(n)=7f(n-1)+l4^{n}}$, por alguna constante${\displaystyle l}$Eso depende del número de sumas realizadas en cada aplicación del algoritmo. Por lo tanto${\displaystyle f(n)=(7+o(1))^{n}}$, es decir, la complejidad asintótica para multiplicar matrices de tamaño${\displaystyle N=2^{n}}$usar el algoritmo de Strassen es ${\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}$Sin embargo, la reducción en el número de operaciones aritméticas conlleva una menor estabilidad numérica ^{[ 9 ]} , y el algoritmo también requiere mucha más memoria que el algoritmo ingenuo. Ambas matrices iniciales deben tener sus dimensiones expandidas a la siguiente potencia de 2, lo que implica almacenar hasta cuatro veces más elementos, y las siete matrices auxiliares contienen cada una una cuarta parte de los elementos de las matrices expandidas.

El algoritmo de Strassen debe compararse con la forma "ingenua" de realizar la multiplicación de matrices, que requeriría 8 multiplicaciones de subbloques en lugar de 7. Esto daría lugar a la complejidad que se espera del enfoque estándar:${\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})}$La comparación de estos dos algoritmos muestra que asintóticamente , el algoritmo de Strassen es más rápido: existe un tamaño${\displaystyle N_{\text{threshold}}}$De modo que las matrices más grandes se multiplican de forma más eficiente con el algoritmo de Strassen que con el método "tradicional". Sin embargo, la afirmación asintótica no implica que el algoritmo de Strassen sea siempre más rápido, incluso para matrices pequeñas, y en la práctica esto no es así: para matrices pequeñas, el coste de las sumas adicionales de bloques de matriz supera el ahorro en el número de multiplicaciones. También existen otros factores no contemplados en el análisis anterior, como la diferencia de coste en el hardware actual entre cargar datos de la memoria a los procesadores y el coste de realizar operaciones con estos datos. Como consecuencia de estas consideraciones, el algoritmo de Strassen se suele utilizar solo en matrices "grandes". Este efecto es aún más pronunciado con algoritmos alternativos como el de Coppersmith y Winograd : aunque asintóticamente es incluso más rápido, el punto de inflexión${\displaystyle N_{\text{threshold}}}$es tan grande que el algoritmo no se suele utilizar en matrices que se encuentran en la práctica.

La descripción anterior indica que las matrices son cuadradas, su tamaño es una potencia de dos y que se debe usar relleno si es necesario. Esta restricción permite dividir las matrices por la mitad, recursivamente, hasta alcanzar el límite de la multiplicación escalar . La restricción simplifica la explicación y el análisis de la complejidad, pero en realidad no es necesaria; ^{[ 12 ]} y, de hecho, rellenar la matriz como se describe aumentará el tiempo de cálculo y puede anular fácilmente el ahorro de tiempo relativamente pequeño obtenido al usar el método inicialmente.

Una buena implementación observará lo siguiente:

• No es necesario ni deseable utilizar el algoritmo de Strassen hasta el límite de escalares. En comparación con la multiplicación de matrices convencional, el algoritmo añade un coste considerable.${\displaystyle O(n^{2})}$carga de trabajo en sumas/restas; por lo tanto, por debajo de cierto tamaño, será mejor usar la multiplicación convencional. Así, por ejemplo, una${\displaystyle 1600\times 1600}$no necesita ser acolchado para${\displaystyle 2048\times 2048}$, ya que podría subdividirse hasta${\displaystyle 25\times 25}$A ese nivel se pueden utilizar matrices y la multiplicación convencional.
• El método se puede aplicar a matrices cuadradas de cualquier dimensión. ^{[ 3 ]} Si la dimensión es par, se dividen por la mitad como se describe. Si la dimensión es impar, primero se aplica un relleno de ceros de una fila y una columna. Este relleno se puede aplicar sobre la marcha y de forma diferida, y las filas y columnas adicionales se descartan a medida que se forma el resultado. Por ejemplo, supongamos que las matrices son${\displaystyle 199\times 199}$. Se pueden dividir de manera que la parte superior izquierda quede${\displaystyle 100\times 100}$y la parte inferior derecha es${\displaystyle 99\times 99}$. Dondequiera que las operaciones lo requieran, dimensiones de${\displaystyle 99}$se rellenan con ceros para${\displaystyle 100}$Primero. Nótese, por ejemplo, que el producto${\displaystyle M_{2}}$se utiliza únicamente en la fila inferior de la salida, por lo que solo se requiere que sea${\displaystyle 99}$filas de altura; y por lo tanto el factor izquierdo${\displaystyle A_{21}+A_{22}}$utilizado para generarlo solo necesita ser${\displaystyle 99}$filas de altura; por consiguiente, no hay necesidad de rellenar esa suma para${\displaystyle 100}$filas; solo es necesario rellenar${\displaystyle A_{22}}$a${\displaystyle 100}$columnas para coincidir${\displaystyle A_{21}}$.

Además, no es necesario que las matrices sean cuadradas. Las matrices no cuadradas se pueden dividir por la mitad utilizando los mismos métodos, obteniendo matrices no cuadradas más pequeñas. Si las matrices son suficientemente no cuadradas, valdrá la pena reducir la operación inicial a más productos cuadrados, utilizando métodos sencillos que son esencialmente ${\displaystyle O(n^{2})}$, por ejemplo:

• Un producto de tamaño${\displaystyle [2N\times N]\ast [N\times 10N]}$se puede hacer como 20 separados${\displaystyle [N\times N]\ast [N\times N]}$operaciones, dispuestas para formar el resultado;
• Un producto de tamaño${\displaystyle [N\times 10N]\ast [10N\times N]}$se puede hacer como 10 por separado${\displaystyle [N\times N]\ast [N\times N]}$operaciones, sumadas para formar el resultado.

Estas técnicas harán que la implementación sea más complicada, en comparación con simplemente rellenar hasta un cuadrado que sea potencia de dos; sin embargo, es razonable suponer que cualquiera que emprenda una implementación de Strassen, en lugar de la multiplicación convencional, dará mayor prioridad a la eficiencia computacional que a la simplicidad de la implementación.

En la práctica, el algoritmo de Strassen se puede implementar para lograr un mejor rendimiento que la multiplicación convencional incluso para matrices tan pequeñas como${\displaystyle 500\times 500}$, para matrices que no son cuadradas en absoluto, y sin requerir espacio de trabajo más allá de los búferes que ya se necesitan para una multiplicación convencional de alto rendimiento. ^{[ 4 ]}

• Complejidad computacional de las operaciones matemáticas
• Eliminación de Gauss-Jordan
• Complejidad computacional de la multiplicación de matrices
• Curva de orden Z
• Algoritmo de Karatsuba , para multiplicar enteros de n dígitos en${\displaystyle O(n^{\log _{2}3})}$en lugar de en${\displaystyle O(n^{2})}$tiempo
  • Un algoritmo de multiplicación compleja similar multiplica dos números complejos usando 3 multiplicaciones reales en lugar de 4.
• El algoritmo de Toom-Cook es una generalización más rápida del algoritmo de Karatsuba que permite la descomposición recursiva de divide y vencerás en más de 2 bloques a la vez.

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7Capítulo 28: Sección 28.2: Algoritmo de Strassen para la multiplicación de matrices, págs.  735 – 741.
• Knuth, Donald (1997). El arte de la programación informática , algoritmos seminuméricos . Vol.  II (3.ª  ed.). Addison-Wesley. ISBN 0-201-89684-2.

• Weisstein, Eric W. "Fórmulas de Strassen" . MundoMatemático .(También incluye fórmulas para la inversión rápida de matrices )
• Tyler J. Earnest, el algoritmo de Strassen en el motor de banda ancha celular