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 (talvez através de uma rede).

A aplicação direta da definição matemática da multiplicação de matrizes resulta em um algoritmo que consome um tempo na ordem de operações de corpo para multiplicar duas matrizes sobre esse corpo ( na notação O-grande). Melhores limites assintóticos para o tempo necessário para multiplicar matrizes são conhecidos desde o Algoritmo de Strassen na década de 1960, mas o tempo ideal (isto é, a complexidade computacional da multiplicação de matrizes) permanece desconhecido. Em setembro de 2025, o melhor limite para a complexidade assintótica de um algoritmo de multiplicação de matrizes era de tempo , obtido por Alman, Duan, Williams, Xu, Xu e Zhou. No entanto, este algoritmo é um algoritmo galáctico devido às grandes constantes ocultas e não pode ser implementado na prática.

Algoritmo iterativo A definição da multiplicação de matrizes estabelece que, se para uma matriz de tamanho e uma matriz de tamanho , então é uma matriz com elementos

A partir disso, um algoritmo simples pode ser construído em loops sobre os índices de 1 até e de 1 até , calculando o valor acima usando um loop aninhado:

Entrada: matrizes e Seja uma nova matriz de tamanho apropriado Para de 1 até : Para de 1 até : Seja Para de 1 até : Defina Defina Retorne

Este algoritmo leva um tempo (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 , caso em que o tempo de execução é , 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 bytes e bytes por linha de cache (ou seja, linhas de cache), o algoritmo acima é subótimo para as matrizes e armazenadas em ordem majoritária por linha. Quando , cada iteração do loop interno (uma varredura simultânea através de uma linha de e uma coluna de ) causa uma falha de cache (*cache miss*) ao acessar um elemento de . Isso significa que o algoritmo incorre em 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.

A variante ideal do algoritmo iterativo para e em disposição por linha é uma versão ladrilhada (*tiled*), onde a matriz é implicitamente dividida em blocos quadrados de tamanho por :

Entrada: matrizes e Seja uma nova matriz de tamanho apropriado Escolha um tamanho de bloco Para de 1 até em passos de : Para de 1 até em passos de : Para de 1 até em passos de : Multiplique e em , isto é: Para de até : Para de até : Seja Para de até : Defina Defina Retorne

No modelo de cache idealizado, este algoritmo incorre em apenas falhas de cache; o divisor equivale a várias ordens de magnitude em máquinas modernas, de modo que os cálculos reais dominam o tempo de execução, e não as falhas de cache.

Algoritmo de divisão e conquista 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 para algum . 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 como seu caso base.

A complexidade deste algoritmo como uma função de é dada pela recorrência

contabilizando as ooito chamadas recursivas em matrizes de tamanho e 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 , 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.

Entradas: matrizes de tamanho , de tamanho . Caso base: se estiver abaixo de um determinado limite, use uma versão desenrolada do algoritmo iterativo. Casos recursivos:

Se , divida horizontalmente:

Senão, se , divida verticalmente:

Caso contrário, . Divida verticalmente e horizontalmente:

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 linhas de cache ideal, cada uma de tamanho bytes, é limitado por

Algoritmos subcúbicos

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 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 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.

Como o algoritmo de Strassen é realmente usado em softwares numéricos práticos e em sistemas de álgebra computacional, a melhoria das constantes ocultas na notação O-grande tem os seus méritos. Segue-se uma tabela que compara os aspetos principais da versão melhorada com base na multiplicação recursiva de matrizes de blocos 2×2 através de 7 multiplicações de matrizes de blocos. Como habitualmente, indica as dimensões da matriz e designa o tamanho da memória.

+ Progresso para a multiplicação recursiva de matrizes em blocos 2x2 do tipo Strassen Ano Referência nº de multiplicações de matrizes por passo nº de adições de matrizes por passo total de operações aritméticas complexidade total de E/S 1969 Strassen 7 18 1971 WinogradComunicação privada com 7 15 2017 Karstadt, Schwartz 7 12 2023 Schwartz, Vaknin 7 12

Sabe-se que um algoritmo do tipo Strassen com um passo de matriz de blocos 2×2 requer pelo menos 7 multiplicações de matrizes de blocos. Em 1976, Probert mostrou que tal algoritmo requer pelo menos 15 adições (incluindo subtrações); no entanto, uma suposição oculta era que os blocos e a matriz de blocos 2×2 são representados na mesma base. Karstadt e Schwartz calcularam em bases diferentes e trocaram 3 adições por transformações de base menos dispendiosas. Também provaram que não se pode descer abaixo de 12 adições por passo utilizando bases diferentes. Em trabalhos subsequentes, Beniamini et el. aplicaram este truque de mudança de base a decomposições mais gerais do que as matrizes de blocos 2×2 e melhoraram a constante principal para os seus tempos de execução.

É uma questão em aberto na ciência da computação teórica até que ponto o algoritmo de Strassen pode ser melhorado em termos de complexidade assintótica. O expoente de multiplicação de matrizes, geralmente denotado por , é o menor número real para o qual quaisquer duas matrizes sobre um corpo podem ser multiplicadas juntas usando operações de corpo. O melhor limite atual para é , obtido por Alman, Duan, Williams, Xu, Xu e Zhou. Este algoritmo, como todos os outros algoritmos recentes nesta linha de investigação, é uma generalização do algoritmo de Coppersmith-Winograd, que foi apresentado por Don Coppersmith e Shmuel Winograd em 1990. A ideia conceptual destes algoritmos é semelhante à do algoritmo de Strassen: concebe-se uma forma de multiplicar duas matrizes com menos de multiplicações, e esta técnica é aplicada recursivamente. No entanto, o coeficiente constante oculto pela notação O-grande é tão grande que estes algoritmos só valem a pena para matrizes que são demasiado grandes para serem processadas nos computadores atuais. Victor Pan propôs algoritmos de multiplicação de matrizes subcúbicos viáveis com um expoente ligeiramente acima de 2.77, mas em contrapartida com um coeficiente constante oculto muito menor.

O Algoritmo de Freivalds é um algoritmo de Monte Carlo simples que, dadas as matrizes , e , verifica em tempo se .

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 (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 . 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.

Algoritmos paralelos e distribuídos

Paralelismo em memória compartilhada