Complexidade computacional da multiplicação de matrizes 📖 Wikipedia

Na ciência da computação teórica, a complexidade computacional da multiplicação de matrizes determina quão rapidamente a operação de multiplicação de matrizes pode ser realizada. Algoritmos de multiplicação de matrizes são uma sub-rotina central em algoritmos teóricos e numéricos para álgebra linear numérica e otimização, portanto encontrar o algoritmo mais rápido para multiplicação de matrizes é de grande relevância prática.

Aplicar diretamente a definição matemática de multiplicação de matrizes dá um algoritmo que requer n³ operações de corpo para multiplicar duas matrizes n × n sobre esse corpo (Θ(n³) em notação big O). Surpreendentemente, existem algoritmos que fornecem melhores tempos de execução do que este algoritmo "escolar" direto. O primeiro a ser descoberto foi o algoritmo de Strassen, concebido por Volker Strassen em 1969 e frequentemente chamado de "multiplicação rápida de matrizes".^[1] O número ótimo de operações de corpo necessárias para multiplicar duas matrizes quadradas n × n a menos de constantes multiplicativas ainda é desconhecido. Esta é uma importante questão em aberto na ciência da computação teórica.

Desde janeiro de 2024 (2024 -01)^[update], a melhor cota na complexidade assintótica de um algoritmo de multiplicação de matrizes é O(n^2.371339).^[2] No entanto, esta e outras melhorias semelhantes a Strassen não são usadas na prática, porque são algoritmos galácticos: o coeficiente constante escondido pela notação big O é tão grande que eles só valem a pena para matrizes grandes demais para serem manipuladas em computadores atuais.^[3][4]

Se A, B são duas matrizes n × n sobre um corpo, então seu produto AB também é uma matriz n × n sobre esse corpo, definida entrada a entrada como $${\displaystyle (AB)_{ij}=\sum _{k=1}^{n}A_{ik}B_{kj}.}$$

 Nota: Para técnicas de implementação (em particular algoritmos paralelos e distribuídos), veja Algoritmo de multiplicação de matrizes.

A abordagem mais simples para calcular o produto de duas matrizes n × n A e B é calcular as expressões aritméticas provenientes da definição de multiplicação de matrizes. Em pseudocódigo:

entrada A e B, ambas matrizes n por n
inicialize C como uma matriz n por n de todos os zeros
para i de 1 até n:
    para j de 1 até n:
        para k de 1 até n:
            C[i][j] = C[i][j] + A[i][k]*B[k][j]
saída C (como A*B)

Este algoritmo requer ⁠${\displaystyle n^{3}}$⁠ multiplicações e ⁠${\displaystyle n^{3}-n^{2}}$⁠ adições de escalares para calcular o produto de duas matrizes quadradas n×n. Sua complexidade computacional é, portanto, ⁠${\displaystyle O(n^{3})}$⁠, em um modelo de computação onde as operações de corpo (adição e multiplicação) levam tempo constante (na prática, este é o caso para números de ponto flutuante, mas não necessariamente para inteiros).

O algoritmo de Strassen melhora a multiplicação de matrizes ingênua através de uma abordagem de dividir para conquistar. A observação chave é que multiplicar duas matrizes 2 × 2 pode ser feito com apenas sete multiplicações, em vez das oito usuais (à custa de 11 operações de adição e subtração adicionais). Isso significa que, tratando as matrizes de entrada n×n como matrizes em blocos 2 × 2, a tarefa de multiplicar duas matrizes n×n pode ser reduzida a sete subproblemas de multiplicação de duas matrizes n/2×n/2. Aplicando isso recursivamente obtém-se um algoritmo que necessita de ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$ operações de corpo.

Ao contrário de algoritmos com complexidade assintótica mais rápida, o algoritmo de Strassen é usado na prática. A estabilidade numérica é reduzida em comparação com o algoritmo ingênuo,^[5] mas é mais rápido em casos onde n > 100 aproximadamente^[6] e aparece em várias bibliotecas, como BLAS.^[7] Algoritmos rápidos de multiplicação de matrizes não podem alcançar estabilidade componente a componente, mas alguns podem ser mostrados como exibindo estabilidade norma a norma.^[8] É muito útil para matrizes grandes sobre domínios exatos, como campos finitos, onde a estabilidade numérica não é um problema.

O expoente da multiplicação de matrizes, geralmente denotado ω, é o menor número real para o qual quaisquer duas matrizes ${\displaystyle n\times n}$ sobre um corpo podem ser multiplicadas usando ${\displaystyle n^{\omega +o(1)}}$ operações de corpo. Esta notação é comumente usada em pesquisa de algoritmos, de modo que algoritmos que usam multiplicação de matrizes como uma sub-rotina tenham cotas no tempo de execução que possam ser atualizadas à medida que as cotas para ω melhoram.

Usando uma cota inferior ingênua e a multiplicação de matrizes escolar para a cota superior, pode-se concluir diretamente que 2 ≤ ω ≤ 3. Se ω = 2 é uma importante questão em aberto na ciência da computação teórica, e há uma linha de pesquisa desenvolvendo algoritmos de multiplicação de matrizes para obter melhores cotas para ω.

Todos os algoritmos recentes nesta linha de pesquisa usam o método laser, uma generalização do algoritmo de Coppersmith–Winograd, que foi dado por Don Coppersmith e Shmuel Winograd em 1990 e foi o melhor algoritmo de multiplicação de matrizes até 2010.^[24] A ideia conceitual destes algoritmos é semelhante à do algoritmo de Strassen: é concebida uma maneira de multiplicar duas matrizes k × k com menos de k³ multiplicações, e esta técnica é aplicada recursivamente. O método laser tem limitações em seu poder: Ambainis, Filmus e Le Gall provam que ele não pode ser usado para mostrar que ω < 2.3725 analisando potências tensoriais cada vez maiores de uma certa identidade de Coppersmith e Winograd, nem ω < 2.3078 para uma ampla classe de variantes desta abordagem.^[25] Em 2022 Duan, Wu e Zhou conceberam uma variante que quebrou a primeira das duas barreiras com ω < 2.37188,^[22] eles o fazem identificando uma fonte de otimização potencial no método laser denominada perda de combinação para a qual eles compensam usando uma versão assimétrica do método de hashing no algoritmo de Coppersmith–Winograd.

No entanto, os exemplos acima são exemplos clássicos de algoritmos galácticos. Por outro lado, o algoritmo de Strassen de 1969 e o algoritmo de Pan de 1978, cujos respectivos expoentes estão ligeiramente acima e abaixo de 2,8, têm coeficientes constantes que os tornam viáveis.^[26]

Henry Cohn, Robert Kleinberg, Balázs Szegedy e Chris Umans colocaram métodos como os algoritmos de Strassen e Coppersmith–Winograd em um contexto grupoteórico inteiramente diferente, utilizando triplos de subconjuntos de grupos finitos que satisfazem uma propriedade de disjunção chamada propriedade do produto triplo (TPP). Eles também fornecem conjecturas que, se verdadeiras, implicariam que existem algoritmos de multiplicação de matrizes com complexidade essencialmente quadrática. Isso implica que o expoente ótimo da multiplicação de matrizes é 2, o que a maioria dos pesquisadores acredita ser de fato o caso.^[4] Uma dessas conjecturas é que famílias de produtos wreath de grupos abelianos com grupos simétricos realizam famílias de triplos de subconjuntos com uma versão simultânea da TPP.^[27][28] Várias de suas conjecturas foram desde então refutadas por Blasiak, Cohn, Church, Grochow, Naslund, Sawin e Umans usando o método de posto de fatia.^[29] Além disso, Alon, Shpilka e Chris Umans mostraram recentemente que algumas dessas conjecturas que implicam multiplicação rápida de matrizes são incompatíveis com outra conjectura plausível, a conjectura do girassol,^[30] que por sua vez está relacionada ao problema do conjunto cap.^[29]

Há uma cota inferior trivial de ⁠${\displaystyle \omega \geq 2}$⁠. Como qualquer algoritmo para multiplicar duas matrizes n × n tem que processar todas as 2n² entradas, há uma cota inferior assintótica trivial de Ω(n²) operações para qualquer algoritmo de multiplicação de matrizes. Assim ⁠${\displaystyle 2\leq \omega <2.37188}$⁠. Não se sabe se ⁠${\displaystyle \omega >2}$⁠. A melhor cota inferior conhecida para a complexidade da multiplicação de matrizes é Ω(n² log(n)), para circuitos aritméticos de coeficientes limitados sobre os números reais ou complexos, e é devida a Ran Raz.^[31]

Sabe-se que, sob o modelo de computação tipicamente estudado, não existe algoritmo de multiplicação de matrizes que use precisamente O(n^ω) operações; deve haver um fator adicional de n^o(1).^[13]

Técnicas semelhantes também se aplicam à multiplicação de matrizes retangulares. O objeto central de estudo é ${\displaystyle \omega (k)}$, que é o menor ${\displaystyle c}$ tal que se pode multiplicar uma matriz de tamanho ${\displaystyle n\times \lceil n^{k}\rceil }$ com uma matriz de tamanho ${\displaystyle \lceil n^{k}\rceil \times n}$ com ${\displaystyle O(n^{c+o(1)})}$ operações aritméticas. Um resultado em complexidade algébrica afirma que multiplicar matrizes de tamanho ${\displaystyle n\times \lceil n^{k}\rceil }$ e ${\displaystyle \lceil n^{k}\rceil \times n}$ requer o mesmo número de operações aritméticas que multiplicar matrizes de tamanho ${\displaystyle n\times \lceil n^{k}\rceil }$ e ${\displaystyle n\times n}$ e de tamanho ${\displaystyle n\times n}$ e ${\displaystyle n\times \lceil n^{k}\rceil }$, portanto isso abrange a complexidade da multiplicação de matrizes retangulares.^[32] Isso generaliza o expoente da multiplicação de matriz quadrada, uma vez que ${\displaystyle \omega (1)=\omega }$.

Como a saída do problema de multiplicação de matrizes tem tamanho ${\displaystyle n^{2}}$, temos ${\displaystyle \omega (k)\geq 2}$ para todos os valores de ${\displaystyle k}$. Se alguém puder provar para alguns valores de ${\displaystyle k}$ entre 0 e 1 que ${\displaystyle \omega (k)\leq 2}$, então tal resultado mostra que ${\displaystyle \omega (k)=2}$ para esses ${\displaystyle k}$. O maior k tal que ${\displaystyle \omega (k)=2}$ é conhecido como o expoente dual da multiplicação de matrizes, geralmente denotado α. α é referido como o "dual" porque mostrar que ${\displaystyle \alpha =1}$ é equivalente a mostrar que ${\displaystyle \omega =2}$. Como o expoente da multiplicação de matrizes, o expoente dual da multiplicação de matrizes às vezes aparece na complexidade de algoritmos em álgebra linear numérica e otimização.^[33]

A primeira cota para α é de Coppersmith em 1982, que mostrou que ${\displaystyle \alpha >0.17227}$.^[34] A melhor cota atual revisada por pares para α é ${\displaystyle \alpha \geq 0.321334}$, dada por Williams, Xu, Xu e Zhou.^[23]

Problemas que têm a mesma complexidade assintótica que a multiplicação de matrizes incluem determinante, inversão de matrizes, eliminação gaussiana (veja a próxima seção). Problemas com complexidade que é expressável em termos de ${\displaystyle \omega }$ incluem polinômio característico, autovalores (mas não autovetores), forma normal de Hermite e forma normal de Smith.^{[carece de fontes?]}

Em seu artigo de 1969, onde provou a complexidade ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$ para computação de matrizes, Strassen provou também que a inversão de matrizes, o determinante e a eliminação gaussiana têm, a menos de uma constante multiplicativa, a mesma complexidade computacional que a multiplicação de matrizes. A prova não faz suposições sobre a multiplicação de matrizes usada, exceto que sua complexidade é ${\displaystyle O(n^{\omega })}$ para algum ${\displaystyle \omega \geq 2}$.

O ponto de partida da prova de Strassen é usar a multiplicação de matrizes em blocos. Especificamente, uma matriz de dimensão par 2n×2n pode ser particionada em quatro blocos n×n $${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.}$$ Sob esta forma, sua inversa é $${\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}},}$$ desde que A e ${\displaystyle {D}-{CA}^{-1}{B}}$ sejam invertíveis.

Assim, a inversa de uma matriz 2n×2n pode ser computada com duas inversões, seis multiplicações e quatro adições ou inversos aditivos de matrizes n×n. Segue-se que, denotando respectivamente por I(n), M(n) e A(n) = n² o número de operações necessárias para inverter, multiplicar e somar matrizes n×n, tem-se $${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).}$$ Se ${\displaystyle n=2^{k},}$ pode-se aplicar esta fórmula recursivamente: $${\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}}}$$ Se ${\displaystyle M(n)\leq cn^{\omega },}$ e ${\displaystyle \alpha =2^{\omega }\geq 4,}$ obtém-se eventualmente $${\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 alguma constante d.

Para matrizes cuja dimensão não é uma potência de dois, a mesma complexidade é alcançada aumentando a dimensão da matriz para uma potência de dois, preenchendo a matriz com linhas e colunas cujas entradas são 1 na diagonal e 0 em outros lugares.

Isso prova a complexidade afirmada para matrizes tais que todas as submatrizes que precisam ser invertidas são de fato invertíveis. Esta complexidade é, portanto, provada para quase todas as matrizes, pois uma matriz com entradas escolhidas aleatoriamente é invertível com probabilidade um.

O mesmo argumento se aplica à decomposição LU, pois, se a matriz A é invertível, a igualdade $${\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 uma decomposição LU em blocos que pode ser aplicada recursivamente a ${\displaystyle A}$ e ${\displaystyle D-CA^{-1}B,}$ para eventualmente obter uma verdadeira decomposição LU da matriz original.

O argumento se aplica também ao determinante, pois resulta da decomposição LU em blocos que $${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}$$

Relacionado ao problema de minimizar o número de operações aritméticas está o de minimizar o número de multiplicações, que é tipicamente uma operação mais cara do que a adição. Um algoritmo ${\displaystyle O(n^{\omega })}$ para multiplicação de matrizes deve necessariamente usar apenas ${\displaystyle O(n^{\omega })}$ operações de multiplicação, mas esses algoritmos são impraticáveis. Melhorando das ${\displaystyle n^{3}}$ multiplicações ingênuas para a multiplicação escolar, matrizes ${\displaystyle 4\times 4}$ em ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ podem ser feitas com 47 multiplicações,^[35] a multiplicação de matrizes ${\displaystyle 3\times 3}$ sobre um anel comutativo pode ser feita em 21 multiplicações^[36][37] (23 se não comutativo^[38]). A cota inferior de multiplicações necessárias é 2mn+2n−m−2 (multiplicação de matrizes n×m com matrizes m×n usando o método de substituição, ${\displaystyle m\geq n\geq 3}$), o que significa que o caso n=3 requer pelo menos 19 multiplicações e n=4 pelo menos 34.^[39] Para n=2, sete multiplicações e 15 adições ótimas são mínimas, em comparação com apenas quatro adições para oito multiplicações.^[40][41]

• Complexidade computacional de operações matemáticas
• Algoritmo CYK § Algoritmo de Valiant
• Algoritmo de Freivalds, um simples algoritmo de Monte Carlo que, dadas as matrizes A, B e C, verifica em tempo Θ(n²) se AB = C.
• Multiplicação de cadeia de matrizes
• Multiplicação de matrizes, para definições abstratas
• Algoritmo de multiplicação de matrizes, para detalhes de implementação prática
• Multiplicação de matriz esparsa por vetor

• Yet another catalogue of fast matrix multiplication algorithms
• Fawzi, A.; Balog, M.; Huang, A.; Hubert, T.; Romera-Paredes, B.; Barekatain, M.; Novikov, A.; Ruiz, F.J.R.; Schrittwieser, J.; Swirszcz, G.; Silver, D.; Hassabis, D.; Kohli, P. (2022). «Discovering faster matrix multiplication algorithms with reinforcement learning». Nature. 610 (7930): 47–53. Bibcode:2022Natur.610...47F. PMC 9534758. PMID 36198780. doi:10.1038/s41586-022-05172-4