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 operações de corpo para multiplicar duas matrizes sobre esse corpo ( 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". O número ótimo de operações de corpo necessárias para multiplicar duas matrizes quadradas a menos de constantes multiplicativas ainda é desconhecido. Esta é uma importante questão em aberto na ciência da computação teórica.

, a melhor cota na complexidade assintótica de um algoritmo de multiplicação de matrizes é . 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.

Algoritmos simples

Se A, B são duas matrizes sobre um corpo, então seu produto AB também é uma matriz sobre esse corpo, definida entrada a entrada como

Algoritmo escolar

A abordagem mais simples para calcular o produto de duas matrizes 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 multiplicações e adições de escalares para calcular o produto de duas matrizes quadradas . Sua complexidade computacional é, portanto, , 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).

Algoritmo de Strassen

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 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 como matrizes em blocos , a tarefa de multiplicar duas matrizes pode ser reduzida a sete subproblemas de multiplicação de duas matrizes . Aplicando isso recursivamente obtém-se um algoritmo que necessita de 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, mas é mais rápido em casos onde aproximadamente e aparece em várias bibliotecas, como BLAS. 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. É muito útil para matrizes grandes sobre domínios exatos, como campos finitos, onde a estabilidade numérica não é um problema.

Expoente da multiplicação de matrizes

thumb|400px|right|Evolução das estimativas do expoente ao longo do tempo para a complexidade computacional da multiplicação de matrizes thumb|400px|right|Detalhe de 1990–2024 + Linha do tempo do expoente da multiplicação de matrizes Ano Cota para Autores 1969 2,8074 Strassen 1978 2,796 Pan 1979 2,780 Bini, Capovani, Romani 1981 2,522 Schönhage 1981 2,517 Romani 1981 2,496 Coppersmith, Winograd 1986 2,479 Strassen 1990 2,3755 Coppersmith, Winograd 2010 2,3737 Stothers 2012 2,3729 Williams 2014 2,3728639 Le Gall 2020 2,3728596 Alman, Williams 2022 2,371866 Duan, Wu, Zhou 2024 2,371552 Williams, Xu, Xu, and Zhou 2024 2,371339 Alman, Duan, Williams, Xu, Xu, and Zhou

O expoente da multiplicação de matrizes, geralmente denotado , é o menor número real para o qual quaisquer duas matrizes sobre um corpo podem ser multiplicadas usando 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 . Se é 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. A ideia conceitual destes algoritmos é semelhante à do algoritmo de Strassen: é concebida uma maneira de multiplicar duas matrizes com menos de 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 analisando potências tensoriais cada vez maiores de uma certa identidade de Coppersmith e Winograd, nem para uma ampla classe de variantes desta abordagem. Em 2022 Duan, Wu e Zhou conceberam uma variante que quebrou a primeira das duas barreiras com , 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.

Reformulação da teoria dos grupos dos algoritmos de multiplicação de matrizes

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. 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. 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. 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, que por sua vez está relacionada ao problema do conjunto cap.

Cotas inferiores para ω

Há uma cota inferior trivial de . Como qualquer algoritmo para multiplicar duas matrizes tem que processar todas as entradas, há uma cota inferior assintótica trivial de operações para qualquer algoritmo de multiplicação de matrizes. Assim . Não se sabe se . A melhor cota inferior conhecida para a complexidade da multiplicação de matrizes é , para circuitos aritméticos de coeficientes limitados sobre os números reais ou complexos, e é devida a Ran Raz.

Sabe-se que, sob o modelo de computação tipicamente estudado, não existe algoritmo de multiplicação de matrizes que use precisamente operações; deve haver um fator adicional de .

Multiplicação de matrizes retangulares

Técnicas semelhantes também se aplicam à multiplicação de matrizes retangulares. O objeto central de estudo é , que é o menor tal que se pode multiplicar uma matriz de tamanho com uma matriz de tamanho com operações aritméticas. Um resultado em complexidade algébrica afirma que multiplicar matrizes de tamanho e requer o mesmo número de operações aritméticas que multiplicar matrizes de tamanho e e de tamanho e , portanto isso abrange a complexidade da multiplicação de matrizes retangulares. Isso generaliza o expoente da multiplicação de matriz quadrada, uma vez que .

Como a saída do problema de multiplicação de matrizes tem tamanho , temos para todos os valores de . Se alguém puder provar para alguns valores de entre 0 e 1 que , então tal resultado mostra que para esses . O maior k tal que é conhecido como o expoente dual da multiplicação de matrizes, geralmente denotado α. α é referido como o "dual" porque mostrar que é equivalente a mostrar que . 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.

A primeira cota para α é de Coppersmith em 1982, que mostrou que . A melhor cota atual revisada por pares para α é , dada por Williams, Xu, Xu e Zhou.

Problemas relacionados

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 incluem polinômio característico, autovalores (mas não autovetores), forma normal de Hermite e forma normal de Smith.

Inversão de matrizes, determinante e eliminação gaussiana Em seu artigo de 1969, onde provou a complexidade 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 é para algum .

O ponto de partida da prova de Strassen é usar a multiplicação de matrizes em blocos. Especificamente, uma matriz de dimensão par pode ser particionada em quatro blocos

Sob esta forma, sua inversa é

desde que e sejam invertíveis.

Assim, a inversa de uma matriz pode ser computada com duas inversões, seis multiplicações e quatro adições ou inversos aditivos de matrizes . Segue-se que, denotando respectivamente por , e o número de operações necessárias para inverter, multiplicar e somar matrizes , tem-se

Se pode-se aplicar esta fórmula recursivamente:

Se e obtém-se eventualmente

para alguma constante .

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 é invertível, a igualdade

define uma decomposição LU em blocos que pode ser aplicada recursivamente a e para eventualmente obter uma verdadeira decomposição LU da matriz original.