Complejidad computacional de la multiplicación de matrices

El método más sencillo para calcular el producto de dos matrices n × n , A y B, consiste en calcular las expresiones aritméticas derivadas de la definición de multiplicación de matrices. En pseudocódigo :

Entrada A y B , ambas matrices n x n. Inicializa C como una matriz n x n de ceros. Para i desde 1 hasta n : Para j desde 1 hasta n : Para k desde 1 hasta n : C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] Salida C (como A * B)

Este algoritmo requiere​${\displaystyle n^{3}}$multiplicaciones y​${\displaystyle n^{3}-n^{2}}$⁠ sumas de escalares para calcular el producto de dos matrices cuadradas n × n . Por lo tanto, su complejidad computacional es ⁠${\displaystyle O(n^{3})}$⁠ , en un modelo de computación donde las operaciones de campo (suma y multiplicación) toman un tiempo constante (en la práctica, este es el caso para los números de punto flotante , pero no necesariamente para los enteros).

El algoritmo de Strassen mejora la multiplicación ingenua de matrices mediante un enfoque de divide y vencerás . La observación clave es que multiplicar dos matrices de 2 × 2 se puede hacer con solo siete multiplicaciones, en lugar de las ocho habituales (a costa de 11 operaciones adicionales de suma y resta). Esto significa que, al tratar las matrices de entrada n × n como matrices de bloques de 2 × 2 , la tarea de multiplicar dos matrices n × n se puede reducir a siete subproblemas de multiplicación de dos matrices n /2× n /2 . Aplicando esto recursivamente se obtiene un algoritmo que requiere${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$operaciones de campo.

A diferencia de los algoritmos con una complejidad asintótica más rápida, el algoritmo de Strassen se utiliza en la práctica. La estabilidad numérica se reduce en comparación con el algoritmo ingenuo, ^{[ 5 ]} pero es más rápido en casos donde n > 100 aproximadamente ^{[ 6 ]} y aparece en varias bibliotecas, como BLAS . ^{[ 7 ]} Los algoritmos rápidos de multiplicación de matrices no pueden lograr estabilidad por componentes , pero se puede demostrar que algunos exhiben estabilidad por normas . ^{[ 8 ]} Es muy útil para matrices grandes sobre dominios exactos como campos finitos , donde la estabilidad numérica no es un problema.

Henry Cohn , Robert Kleinberg , Balázs Szegedy y Chris Umans colocaron métodos como los algoritmos de Strassen y Coppersmith-Winograd en un contexto de teoría de grupos completamente diferente, al utilizar tríos de subconjuntos de grupos finitos que satisfacen una propiedad de disyunción llamada propiedad del producto triple (TPP) . También presentan conjeturas que, de ser ciertas, implicarían que existen algoritmos de multiplicación de matrices con complejidad esencialmente cuadrática. Esto implica que el exponente óptimo de la multiplicación de matrices es 2, lo cual la mayoría de los investigadores cree que es cierto. ^{[ 4 ]} Una de estas conjeturas es que las familias de productos de coronas de grupos abelianos con grupos simétricos realizan familias de tríos de subconjuntos con una versión simultánea de la TPP. ^{[ 27 ] [ 28 ]} Varias de sus conjeturas han sido posteriormente refutadas por Blasiak, Cohn, Church, Grochow, Naslund, Sawin y Umans utilizando el método Slice Rank. ^{[ 29 ]} Además, Alon, Shpilka y Chris Umans han demostrado recientemente que algunas de estas conjeturas que implican una multiplicación rápida de matrices son incompatibles con otra conjetura plausible, la conjetura del girasol , ^{[ 30 ]} que a su vez está relacionada con el problema del conjunto de tapas. ^{[ 29 ]}

Existe un límite inferior trivial de ⁠${\displaystyle \omega \geq 2}$Dado que cualquier algoritmo para multiplicar dos matrices n × n tiene que procesar todas las 2 n ² entradas, existe una cota inferior asintótica trivial de Ω( n ² ) operaciones para cualquier algoritmo de multiplicación de matrices. Por lo tanto ,${\displaystyle 2\leq \omega <2.37188}$Se desconoce si${\displaystyle \omega >2}$⁠ . La cota inferior más conocida para la complejidad de la multiplicación de matrices es Ω( n ² log( n )) , para circuitos aritméticos de coeficientes acotados sobre los números reales o complejos, y se debe a Ran Raz . ^{[ 31 ]}

Se sabe que, bajo el modelo de computación típicamente estudiado, no existe ningún algoritmo de multiplicación de matrices que utilice precisamente O ( n ^ω ) operaciones; debe haber un factor adicional de n ^o(1) . ^{[ 13 ]}

Técnicas similares también se aplican a la multiplicación de matrices rectangulares. El objeto central de estudio es${\displaystyle \omega (k)}$, que es el más pequeño${\displaystyle c}$de tal manera que se pueda multiplicar una matriz de tamaño${\displaystyle n\times \lceil n^{k}\rceil }$con una matriz de tamaño${\displaystyle \lceil n^{k}\rceil \times n}$con${\displaystyle O(n^{c+o(1)})}$operaciones aritméticas. Un resultado en complejidad algebraica establece que multiplicar matrices de tamaño${\displaystyle n\times \lceil n^{k}\rceil }$y${\displaystyle \lceil n^{k}\rceil \times n}$requiere el mismo número de operaciones aritméticas que multiplicar matrices de tamaño${\displaystyle n\times \lceil n^{k}\rceil }$y${\displaystyle n\times n}$y de tamaño${\displaystyle n\times n}$y${\displaystyle n\times \lceil n^{k}\rceil }$, por lo que esto abarca la complejidad de la multiplicación de matrices rectangulares. ^{[ 32 ]} Esto generaliza el exponente de la multiplicación de matrices cuadradas , ya que${\displaystyle \omega (1)=\omega}$.

Dado que la salida del problema de multiplicación de matrices es de tamaño${\displaystyle n^{2}}$, tenemos${\displaystyle \omega (k)\geq 2}$para todos los valores de${\displaystyle k}$. Si se puede demostrar para algunos valores de${\displaystyle k}$entre 0 y 1 que${\displaystyle \omega (k)\leq 2}$, entonces tal resultado demuestra que${\displaystyle \omega (k)=2}$para aquellos${\displaystyle k}$. El k más grande tal que${\displaystyle \omega (k)=2}$se conoce como el exponente de multiplicación de matrices dual , generalmente denotado α . α se denomina " dual " porque muestra que${\displaystyle \alpha =1}$es equivalente a demostrar que${\displaystyle \omega =2}$. Al igual que el exponente de la multiplicación de matrices, el exponente de la multiplicación de matrices dual aparece a veces en la complejidad de los algoritmos en álgebra lineal numérica y optimización. ^{[ 33 ]}

La primera cota para α la estableció Coppersmith en 1982, quien demostró que${\displaystyle \alpha >0.17227}$. ^{[ 34 ]} El mejor límite revisado por pares actual para α es${\displaystyle \alpha \geq 0.321334}$, dado por Williams, Xu, Xu y Zhou. ^{[ 23 ]}

En su artículo de 1969, donde demostró la complejidad${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$Para el cálculo de matrices, Strassen también demostró que la inversión de matrices , el determinante y la eliminación gaussiana tienen, salvo una constante multiplicativa, la misma complejidad computacional que la multiplicación de matrices. La demostración no hace ninguna suposición sobre la multiplicación de matrices que se utiliza, excepto que su complejidad es${\displaystyle O(n^{\omega })}$para algunos${\displaystyle \omega \geq 2}$.

El punto de partida de la demostración de Strassen es el uso de la multiplicación de matrices por bloques . Específicamente, una matriz de dimensión par 2n × 2n puede particionarse en cuatro bloques de n × n .$${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.}$$ Bajo esta forma, su inversa es $${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&-{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}\\-({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&({D}-{CA}^{-1}{B})^{-1}\end{bmatrix}},}$$ siempre que A y${\displaystyle {D}-{CA}^{-1}{B}}$son invertibles.

Así, la inversa de una matriz de 2n × 2n se puede calcular con dos inversiones, seis multiplicaciones y cuatro sumas o inversas aditivas de matrices de n × n . De ello se deduce que, denotando respectivamente por I ( n ) , M ( n ) y A ( n ) = n² el número de operaciones necesarias para invertir, multiplicar y sumar matrices ^de n × n , se tiene $${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).}$$ Si${\displaystyle n=2^{k},}$Esta fórmula puede aplicarse de forma recursiva: $${\displaystyle {\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\,\,\,\vdots \end{aligned}}}$$ Si${\displaystyle M(n)\leq cn^{\omega },}$y${\displaystyle \alpha =2^{\omega }\geq 4,}$uno finalmente lo consigue $${\displaystyle {\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\\&\leq d(2^{k})^{\omega }\end{aligned}}}$$ para alguna constante d .

Para matrices cuya dimensión no es una potencia de dos, se alcanza la misma complejidad aumentando la dimensión de la matriz a una potencia de dos, rellenando la matriz con filas y columnas cuyos valores sean 1 en la diagonal y 0 en el resto.

Esto demuestra la complejidad afirmada para matrices tales que todas las submatrices que deben invertirse son, en efecto, invertibles. Por lo tanto, esta complejidad queda demostrada para casi todas las matrices, ya que una matriz con entradas elegidas al azar es invertible con probabilidad uno.

El mismo argumento se aplica a la descomposición LU , ya que, si la matriz A es invertible, la igualdad $${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}}$$ define una descomposición LU en bloques que puede aplicarse recursivamente a${\displaystyle A}$y${\displaystyle D-CA^{-1}B,}$para obtener finalmente una verdadera descomposición LU de la matriz original.

El argumento también se aplica al determinante, ya que resulta de la descomposición LU por bloques que $${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}$$

Relacionado con el problema de minimizar el número de operaciones aritméticas está minimizar el número de multiplicaciones, que suele ser una operación más costosa que la suma.${\displaystyle O(n^{\omega })}$El algoritmo para la multiplicación de matrices debe necesariamente utilizar únicamente${\displaystyle O(n^{\omega })}$operaciones de multiplicación, pero estos algoritmos no son prácticos. Mejorando desde el ingenuo${\displaystyle n^{3}}$multiplicaciones para la multiplicación del libro de texto escolar,${\displaystyle 4\times 4}$matrices en${\displaystyle \mathbb {Z} /2\mathbb {Z} }$se puede hacer con 47 multiplicaciones, ^{[ 36 ]}${\displaystyle 3\times 3}$La multiplicación de matrices sobre un anillo conmutativo se puede realizar en 21 multiplicaciones ^{[ 37 ] [ 38 ]} (23 si no es conmutativo ^{[ 39 ]} ). El límite inferior de multiplicaciones necesarias es 2 mn +2 n − m −2 (multiplicación de matrices n × m con matrices m × n usando el método de sustitución,${\displaystyle m\geq n\geq 3}$), lo que significa que el caso n=3 requiere al menos 19 multiplicaciones y el caso n=4 al menos 34. ^{[ 40 ]} Para n=2, el mínimo óptimo son siete multiplicaciones y 15 sumas, en comparación con solo cuatro sumas para ocho multiplicaciones. ^{[ 41 ] [ 42 ]}