Algoritmo de multiplicação de matrizes
Como a multiplicação de matrizes é uma operação central em muitos algoritmos numéricos, muito trabalho tem sido investido para tornar os algoritmos de multiplicação de matrizes eficientes. As aplicações da multiplicação de matrizes em problemas computacionais são encontradas em muitos campos, incluindo computação científica e reconhecimento de padrões, e em problemas aparentemente não relacionados, como a contagem de caminhos através de um grafo. Muitos algoritmos diferentes foram projetados para multiplicar matrizes em diferentes tipos de hardware, incluindo sistemas paralelos e distribuídos, onde o trabalho computacional é espalhado por múltiplos processadores.
A definição da multiplicação de matrizes estabelece que, se C = A B {\displaystyle C=AB} para uma matriz A {\displaystyle A} de tamanho n × m {\displaystyle n\times m} e uma matriz B {\displaystyle B} de tamanho m × p {\displaystyle m\times p} , então C {\displaystyle C} é uma matriz n × p {\displaystyle n\times p} com elementos A partir disso, um algoritmo simples pode ser construído em loops sobre os índices i {\displaystyle i} de 1 até n {\displaystyle n} e j {\displaystyle j} de 1 até p {\displaystyle p} , calculando o valor acima usando um loop aninhado: Este algoritmo leva um tempo Θ ( n m p ) {\displaystyle \Theta (nmp)} (na notação assintótica). Uma simplificação comum para fins de análise de algoritmos é assumir que as entradas são todas matrizes quadradas de tamanho n × n {\displaystyle n\times n} , caso em que o tempo de execução é Θ ( n 3 ) {\displaystyle \Theta (n^{3})} , ou seja, cúbico em relação ao tamanho da dimensão.
Comportamento do cache
Os três loops na multiplicação iterativa de matrizes podem ser arbitrariamente trocados entre si sem afetar a correção ou o tempo de execução assintótico. No entanto, a ordem pode ter um impacto considerável no desempenho prático devido aos padrões de acesso à memória e ao uso do cache do processador; qual ordem é melhor também depende de as matrizes estarem armazenadas em ordem majoritária por linha, ordem majoritária por coluna ou em uma mistura de ambas. Em particular, no caso idealizado de um cache totalmente associativo que consiste em M {\displaystyle M} bytes e b {\displaystyle b} bytes por linha de cache (ou seja, M / b {\displaystyle M/b} linhas de cache), o algoritmo acima é subótimo para as matrizes A {\displaystyle A} e B {\displaystyle B} armazenadas em ordem majoritária por linha. Quando n > M / b {\displaystyle n>M/b} , cada iteração do loop interno (uma varredura simultânea através de uma linha de A {\displaystyle A} e uma coluna de B {\displaystyle B} ) causa uma falha de cache (*cache miss*) ao acessar um elemento de B {\displaystyle B} . Isso significa que o algoritmo incorre em Θ ( n 3 ) {\displaystyle \Theta (n^{3})} falhas de cache no pior caso. Até 2010, a velocidade das memórias em comparação com a dos processadores era tal que as falhas de cache, e não os cálculos reais, dominavam o tempo de execução para matrizes de tamanho considerável.
Uma alternativa ao algoritmo iterativo é o algoritmo de divisão e conquista para multiplicação de matrizes. Este baseia-se no particionamento em blocos o que funciona para todas as matrizes quadradas cujas dimensões são potências de dois, ou seja, as formas são 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}} para algum n {\displaystyle n} . O produto matricial passa a ser que consiste em oito multiplicações de pares de submatrizes, seguidas por uma etapa de adição. O algoritmo de divisão e conquista calcula as multiplicações menores recursivamente, usando a multiplicação por escalar c 11 = a 11 b 11 {\displaystyle c_{11}=a_{11}b_{11}} como seu caso base. A complexidade deste algoritmo como uma função de n {\displaystyle n} é dada pela recorrência contabilizando as ooito chamadas recursivas em matrizes de tamanho n / 2 {\displaystyle n/2} e Θ ( n 2 ) {\displaystyle \Theta (n^{2})} para somar os quatro pares de matrizes resultantes elemento a elemento. A aplicação do teorema mestre para recorrências de divisão e conquista mostra que esta recursão tem a solução T ( n ) = Θ ( n 3 ) {\displaystyle T(n)=\Theta (n^{3})} , a mesma do algoritmo iterativo.
Matrizes não quadradas
Uma variante deste algoritmo que funciona para matrizes de formatos arbitrários e é mais rápida na prática divide as matrizes em duas em vez de quatro submatrizes, conforme indicado a seguir. Dividir uma matriz agora significa dividi-la em duas partes de tamanho igual, ou o mais próximo possível de tamanhos iguais no caso de dimensões ímpares.
Comportamento do cache
A taxa de falhas de cache da multiplicação recursiva de matrizes é a mesma de uma versão iterativa ladrilhada, mas, ao contrário desse algoritmo, o algoritmo recursivo é alheio ao cache (*cache-oblivious*): nenhum parâmetro de ajuste é necessário para obter o desempenho ideal do cache, e ele se comporta bem em um ambiente de multiprogramação onde os tamanhos do cache são efetivamente dinâmicos devido a outros processos que ocupam espaço no cache. (O algoritmo iterativo simples também é alheio ao cache, mas muito mais lento na prática se a disposição da matriz não for adaptada ao algoritmo.) O número de falhas de cache incorridas por este algoritmo, em uma máquina com M {\displaystyle M} linhas de cache ideal, cada uma de tamanho b {\displaystyle b} bytes, é limitado por:13
Existem algoritmos que fornecem tempos de execução melhores do que os diretos. O primeiro a ser descobordo foi o Algoritmo de Strassen, projetado por Volker Strassen em 1969 e frequentemente chamado de "multiplicação rápida de matrizes". Baseia-se em uma maneira de multiplicar duas matrizes 2×2 que requer apenas 7 multiplicações (em vez das 8 usuais), à custa de várias operações adicionais de adição e subtração. A aplicação recursiva disto resulta num algoritmo com um custo multiplicativo de O ( n log 2 7 ) ≈ O ( n 2.807 ) {\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})} . O algoritmo de Strassen é mais complexo e a estabilidade numérica é reduzida em comparação com o algoritmo ingênuo, mas é mais rápido em casos onde n > 100 {\displaystyle n>100} ou algo próximo disso, e aparece em várias bibliotecas, como a BLAS. É muito útil para matrizes grandes sobre domínios exatos, como corpos finitos, onde a estabilidade numérica não é um problema.
AlphaTensor
Em 2022, a DeepMind introduziu o AlphaTensor, uma rede neural que utilizou uma analogia com um jogo de um jogador para inventar milhares de algoritmos de multiplicação de matrizes, incluindo alguns descobertos anteriormente por humanos e outros não. As operações foram restritas ao corpo base não comutativo (aritmética normal) e ao corpo finito Z / 2 Z {\displaystyle \mathbb {Z} /2\mathbb {Z} } (aritmética módulo 2). O melhor algoritmo "prático" encontrado (decomposição explícita de posto baixo de um tensor de multiplicação de matrizes) foi executado em O ( n 2.778 ) {\displaystyle O(n^{2.778})} . Encontrar decomposições de posto baixo de tais tensores é NP-difícil; a multiplicação ideal mesmo para matrizes 3×3 permanece desconhecida, mesmo em corpos comutativos. Em matrizes 4×4, o AlphaTensor descobriu inesperadamente uma solução com 47 passos de multiplicação, uma melhoria em relação aos 49 exigidos pelo algoritmo de Strassen de 1969, embora restrito à aritmética módulo 2. Da mesma forma, o AlphaTensor resolveu matrizes 5×5 com 96 passos em vez dos 98 de Strassen. Com base na surpreendente descoberta de que tais melhorias existem, outros investigadores conseguiram rapidamente encontrar um algoritmo autónomo semelhante para 4×4 e, separadamente, otimizaram o algoritmo de 96 passos para 5×5 da Deepmind para 95 passos em aritmética módulo 2 e para 97 em aritmética normal. Alguns algoritmos eram completamente novos: por exemplo, o formato (4, 5, 5) foi melhorado para 76 passos a partir de uma base de 80, tanto em aritmética normal quanto módulo 2.
Paralelismo em memória compartilhada
O algoritmo de divisão e conquista esboçado anteriormente pode ser paralelizado de duas maneiras para multiprocessadores de memória compartilhada. Estas baseiam-se no facto de que as oito multiplicações recursivas de matrizes em podem ser executadas independentemente umas das outras, tal como as quatro somas (embora o algoritmo precise de "reunir" (*join*) as multiplicações antes de efetuar as somas). Explorando o paralelismo total do problema, obtém-se um algoritmo que pode ser expresso em Pseudocódigo no estilo fork-join: Procedimento multiply ( C , A , B ) {\displaystyle {\text{multiply}}(C,A,B)} : Procedimento add ( C , T ) {\displaystyle {\text{add}}(C,T)} adiciona T {\displaystyle T} em C {\displaystyle C} , elemento a elemento:
Algoritmos distribuídos e que evitam comunicação
Nas arquiteturas modernas com memória hierárquica, o custo de carregar e armazenar elementos de matrizes de entrada tende a dominar o custo da aritmética. Numa única máquina, esta é a quantidade de dados transferidos entre a RAM e o cache, enquanto numa máquina de memória distribuída com múltiplos nós, é a quantidade transferida entre os nós; em ambos os casos, designa-se por largura de banda de comunicação. O algoritmo ingênuo que utiliza três loops aninhados consome Ω ( n 3 ) {\displaystyle \Omega (n^{3})} de largura de banda de comunicação. O Algoritmo de Cannon, também conhecido como algoritmo 2D, é um algoritmo que evita comunicação que particiona cada matriz de entrada numa matriz de blocos cujos elementos são submatrizes de tamanho M / 3 {\displaystyle {\sqrt {M/3}}} por M / 3 {\displaystyle {\sqrt {M/3}}} , onde M {\displaystyle M} é o tamanho da memória rápida. O algoritmo ingênuo é então utilizado sobre as matrizes de blocos, calculando os produtos das submatrizes inteiramente na memória rápida. Isto reduz a largura de banda de comunicação para O ( n 3 / M ) {\displaystyle O(n^{3}/{\sqrt {M}})} , o que é assintoticamente ideal (fornecendo algoritmos que executam Ω ( n 3 ) {\displaystyle \Omega (n^{3})} computações).
Algoritmos para malhas
Existe uma variedade de algoritmos para multiplicação em malhas. Para a multiplicação de duas matrizes n × n {\displaystyle n\times n} numa malha bidimensional padrão utilizando o algoritmo 2D de Cannon, a multiplicação pode ser concluída em 3 n − 2 {\displaystyle 3n-2} passos, embora este número seja reduzido para metade em computações repetidas. A estrutura padrão é ineficiente porque os dados das duas matrizes não chegam simultaneamente e devem ser preenchidos com zeros. O resultado é ainda mais rápido numa malha de duas camadas com fios cruzados, onde são necessários apenas 2 n − 1 {\displaystyle 2n-1} passos. O desempenho melhora ainda mais para computações repetidas, levando a 100% de eficiência. A estrutura de malha com fios cruzados pode ser vista como um caso especial de uma estrutura de processamento não planar (ou seja, multicamadas).
