miniaturadaimagem|Para multiplicar matrizes (2x2), são utilizados os produtos das somas e diferenças dos elementos. Na imagem, cada produto é colocado em uma moldura colorida separada, e a forma como eles são combinados na matriz final é indicada por raios que saem deles.
Em álgebra linear, o algoritmo de Strassen, em homenagem a Volker Strassen, é um algoritmo de multiplicação de matrizes. É mais rápido que o algoritmo de multiplicação de matrizes padrão para matrizes grandes, com melhor complexidade assintótica ( versus ), embora o algoritmo ingênuo seja frequentemente melhor para matrizes menores. O algoritmo de Strassen é mais lento do que os algoritmos conhecidos mais rápidos para matrizes extremamente grandes, mas tais algoritmos galácticos não são úteis na prática, pois são muito mais lentos para matrizes de tamanho prático. Para matrizes pequenas, existem algoritmos ainda mais rápidos.
O algoritmo de Strassen funciona para qualquer anel, como soma/multiplicação, mas não para todos os semianéis, como min-plus ou álgebra booliana, onde o algoritmo ingênuo ainda funciona, sendo a chamada multiplicação de matrizes combinatória.
História Volker Strassen publicou este algoritmo pela primeira vez em 1969 e, assim, provou que o algoritmo de multiplicação de matrizes geral não era ótimo. A publicação do algoritmo de Strassen resultou em mais pesquisas sobre multiplicação de matrizes que levaram a limites inferiores assintóticos e a limites superiores computacionais melhorados.
Algoritmo thumb|800px|centro|A coluna esquerda visualiza os cálculos necessários para determinar o resultado de uma multiplicação de matrizes 2x2. A multiplicação de matrizes ingênua requer uma multiplicação para cada "1" da coluna esquerda. Cada uma das outras colunas (M1-M7) representa uma única das 7 multiplicações no algoritmo de Strassen. A soma das colunas M1-M7 dá o mesmo resultado que a multiplicação de matrizes completa à esquerda.
Sejam , duas matrizes quadradas sobre um anel , por exemplo, matrizes cujas entradas são números inteiros ou números reais. O objetivo da multiplicação de matrizes é calcular o produto matricial . A seguinte exposição do algoritmo assume que todas essas matrizes têm tamanhos que são potências de dois (isto é, ), mas isso é apenas conceitualmente necessário — se as matrizes , não são do tipo , as linhas e colunas "faltantes" podem ser preenchidas com zeros para obter matrizes com tamanhos de potências de dois — embora implementações reais do algoritmo não façam isso na prática.
O algoritmo de Strassen particiona , e em matrizes blocos de tamanhos iguais
com . O algoritmo ingênuo seria:
Esta construção não reduz o número de multiplicações: ainda são necessárias 8 multiplicações de blocos de matrizes para calcular as matrizes , o mesmo número de multiplicações necessário ao usar a multiplicação de matrizes padrão.
O algoritmo de Strassen define, em vez disso, novos valores:
usando apenas 7 multiplicações (uma para cada ) em vez de 8. Podemos agora expressar os em termos de :
Iteramos recursivamente este processo de divisão até que as submatrizes degenerem em números (elementos do anel ). Se, como mencionado acima, a matriz original tivesse um tamanho que não é potência de 2, então o produto resultante terá linhas e colunas zero assim como e , e estas serão então removidas neste ponto para obter a matriz (menor) que realmente queríamos.
Implementações práticas do algoritmo de Strassen alternam para métodos padrão de multiplicação de matrizes para submatrizes suficientemente pequenas, para as quais esses algoritmos são mais eficientes. O ponto de transição específico para o qual o algoritmo de Strassen é mais eficiente depende da implementação e do hardware. Autores anteriores estimaram que o algoritmo de Strassen é mais rápido para matrizes com larguras de 32 a 128 para implementações otimizadas. No entanto, observou-se que este ponto de transição tem aumentado nos últimos anos, e um estudo de 2010 descobriu que mesmo uma única etapa do algoritmo de Strassen muitas vezes não é benéfica em arquiteturas atuais, em comparação com uma multiplicação tradicional altamente otimizada, até que os tamanhos das matrizes excedam 1000 ou mais, e mesmo para tamanhos de matriz de vários milhares, o benefício é tipicamente marginal na melhor das hipóteses (cerca de 10% ou menos). Um estudo mais recente (2016) observou benefícios para matrizes tão pequenas quanto 512 e um benefício em torno de 20%.
Melhorias no algoritmo de Strassen
É possível reduzir o número de adições de matrizes usando a seguinte forma descoberta por Winograd em 1971:
onde .
Isso reduz o número de adições e subtrações de matrizes de 18 para 15. O número de multiplicações de matrizes continua sendo 7, e a complexidade assintótica é a mesma.
O algoritmo foi posteriormente otimizado em 2017 usando uma base alternativa, reduzindo o número de adições de matrizes por etapa bilinear para 12, mantendo o número de multiplicações de matrizes, e novamente em 2023:
Complexidade assintótica
O esboço do algoritmo acima mostrou que podemos nos livrar de apenas 7, em vez das tradicionais 8, multiplicações matriz-matriz para os sub-blocos da matriz. Por outro lado, é necessário fazer adições e subtrações de blocos, embora isso não seja preocupante para a complexidade geral: Adicionar matrizes de tamanho requer apenas operações, enquanto a multiplicação é substancialmente mais cara (tradicionalmente operações de adição ou multiplicação).
A questão é quantas operações exatamente são necessárias para o algoritmo de Strassen e como isso se compara com a multiplicação de matrizes padrão que leva aproximadamente (onde ) operações aritméticas, ou seja, uma complexidade assintótica .
O número de adições e multiplicações necessárias no algoritmo de Strassen pode ser calculado como segue: seja o número de operações para uma matriz . Então, pela aplicação recursiva do algoritmo de Strassen, vemos que , para alguma constante que depende do número de adições realizadas em cada aplicação do algoritmo. Portanto, , ou seja, a complexidade assintótica para multiplicar matrizes de tamanho usando o algoritmo de Strassen é . A redução no número de operações aritméticas, no entanto, tem o preço de uma estabilidade numérica um pouco reduzida, e o algoritmo também requer significativamente mais memória em comparação com o algoritmo ingênuo. Ambas as matrizes iniciais devem ter suas dimensões expandidas para a próxima potência de 2, o que resulta no armazenamento de até quatro vezes mais elementos, e as sete matrizes auxiliares contêm cada uma um quarto dos elementos das matrizes expandidas.
O algoritmo de Strassen precisa ser comparado com a maneira "ingênua" de fazer a multiplicação de matrizes que exigiria 8 em vez de 7 multiplicações de sub-blocos. Isso daria então origem à complexidade que se espera da abordagem padrão: . A comparação desses dois algoritmos mostra que, assintoticamente, o algoritmo de Strassen é mais rápido: existe um tamanho tal que matrizes maiores são multiplicadas de forma mais eficiente com o algoritmo de Strassen do que da maneira "tradicional". No entanto, a afirmação assintótica não implica que o algoritmo de Strassen seja sempre mais rápido, mesmo para matrizes pequenas, e na prática este não é o caso: Para matrizes pequenas, o custo das adições adicionais de blocos de matrizes supera as economias no número de multiplicações. Há também outros fatores não capturados pela análise acima, como a diferença no custo em hardware atual entre carregar dados da memória para os processadores versus o custo de realmente realizar operações sobre esses dados. Como consequência desses tipos de considerações, o algoritmo de Strassen é tipicamente usado apenas em matrizes "grandes". Esse tipo de efeito é ainda mais pronunciado com algoritmos alternativos como o de Coppersmith e Winograd: Embora assintoticamente ainda mais rápidos, o ponto de transição é tão grande que o algoritmo geralmente não é usado em matrizes que encontramos na prática.
Posto ou complexidade bilinear A complexidade bilinear ou posto de um mapa bilinear é um conceito importante na complexidade assintótica da multiplicação de matrizes. O posto de um mapa bilinear sobre um corpo F é definido como (um tanto quanto um abuso de notação)
Em outras palavras, o posto de um mapa bilinear é o comprimento de seu cálculo bilinear mais curto. A existência do algoritmo de Strassen mostra que o posto da multiplicação de matrizes não é maior que sete. Para ver isso, vamos expressar este algoritmo (juntamente com o algoritmo padrão) como tal cálculo bilinear. No caso de matrizes, os espaços duais A* e B* consistem em mapas para o corpo F induzidos por um produto duplo escalar (ou seja, neste caso, a soma de todas as entradas de um produto de Hadamard.) Algoritmo padrão Algoritmo de Strassen 1 2 3 4 5 6 7 8 Pode-se mostrar que o número total de multiplicações elementares necessárias para a multiplicação de matrizes está assintoticamente fortemente ligado ao posto , isto é, , ou mais especificamente, como as constantes são conhecidas, . Uma propriedade útil do posto é que ele é submultiplicativo para produtos tensoriais, e isso permite mostrar que a multiplicação de matrizes pode ser realizada com não mais que multiplicações elementares para qualquer . (Este produto tensorial -vezes do mapa de multiplicação de matrizes consigo mesmo — uma -ésima potência tensorial — é realizado pela etapa recursiva no algoritmo mostrado.)
Comportamento de cache O algoritmo de Strassen é cache-oblivious. A análise de seu comportamento de cache mostrou que ele incorre em
falhas de cache durante sua execução, assumindo um cache idealizado de tamanho (isto é, com linhas de comprimento ).
Considerações de implementação A descrição acima afirma que as matrizes são quadradas e o tamanho é uma potência de dois, e que o preenchimento com zeros deve ser usado se necessário. Essa restrição permite que as matrizes sejam divididas ao meio, recursivamente, até o limite da multiplicação escalar. A restrição simplifica a explicação e a análise de complexidade, mas não é realmente necessária; e, de fato, preencher a matriz como descrito aumentará o tempo de computação e pode facilmente eliminar as pequenas economias de tempo obtidas pelo uso do método em primeiro lugar.
Uma boa implementação observará o seguinte:
Não é necessário nem desejável usar o algoritmo de Strassen até o limite dos escalares. Em comparação com a multiplicação de matrizes convencional, o algoritmo adiciona uma carga de trabalho considerável em adições/subtrações; portanto, abaixo de um certo tamanho, será melhor usar a multiplicação convencional. Assim, por exemplo, uma matriz não precisa ser preenchida para , pois poderia ser subdividida até matrizes e a multiplicação convencional pode então ser usada nesse nível. O método pode de fato ser aplicado a matrizes quadradas de qualquer dimensão. Se a dimensão for par, elas são divididas ao meio como descrito. Se a dimensão for ímpar, o preenchimento com zero por uma linha e uma coluna é aplicado primeiro. Esse preenchimento pode ser aplicado sob demanda e de forma preguiçosa, e as linhas e colunas extras são descartadas à medida que o resultado é formado. Por exemplo, suponha que as matrizes sejam . Elas podem ser divididas de modo que a parte superior esquerda seja e a inferior direita seja . Onde as operações exigirem, as dimensões de são preenchidas com zero para primeiro. Observe, por exemplo, que o produto é usado apenas na linha inferior da saída, portanto, é necessário apenas ter linhas de altura; e assim o fator esquerdo usado para gerá-lo precisa ter apenas linhas de altura; consequentemente, não há necessidade de preencher essa soma para linhas; só é necessário preencher para colunas para corresponder a .