Algoritmo de Strassen

Volker Strassen publicou este algoritmo pela primeira vez em 1969 e, assim, provou que o algoritmo de multiplicação de matrizes geral n 3 {\displaystyle n^{3}} 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.

Sejam A {\displaystyle A} , B {\displaystyle B} duas matrizes quadradas sobre um anel R {\displaystyle {\mathcal {R}}} , 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 C = A B {\displaystyle C=AB} . A seguinte exposição do algoritmo assume que todas essas matrizes têm tamanhos que são potências de dois (isto é, A , B , C ∈ Matr 2 n × 2 n ⁡ ( R ) {\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})} ), mas isso é apenas conceitualmente necessário — se as matrizes A {\displaystyle A} , B {\displaystyle B} não são do tipo 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}} , 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 A {\displaystyle A} , B {\displaystyle B} e C {\displaystyle C} em matrizes blocos de tamanhos iguais

É possível reduzir o número de adições de matrizes usando a seguinte forma descoberta por Winograd em 1971: [ a b c d ] [ A C B D ] = [ t + b × B w + v + ( a + b − c − d ) × D w + u + d × ( B + C − A − D ) w + u + v ] {\displaystyle {\begin{bmatrix}a&b\\c&d\end{bmatrix}}{\begin{bmatrix}A&C\\B&D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&w+v+(a+b-c-d){\color {red}\times }D\\w+u+d{\color {red}\times }(B+C-A-D)&w+u+v\end{bmatrix}}} onde t = a × A , u = ( c − a ) × ( C − D ) , v = ( c + d ) × ( C − A ) , w = t + ( c + d − a ) × ( A + D − C ) {\displaystyle t=a{\color {red}\times }A,\;u=(c-a){\color {red}\times }(C-D),\;v=(c+d){\color {red}\times }(C-A),\;w=t+(c+d-a){\color {red}\times }(A+D-C)} . 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:

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 N / 2 {\displaystyle N/2} requer apenas ( N / 2 ) 2 {\displaystyle (N/2)^{2}} operações, enquanto a multiplicação é substancialmente mais cara (tradicionalmente 2 ( N / 2 ) 3 {\displaystyle 2(N/2)^{3}} 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 2 N 3 {\displaystyle 2N^{3}} (onde N = 2 n {\displaystyle N=2^{n}} ) operações aritméticas, ou seja, uma complexidade assintótica Θ ( N 3 ) {\displaystyle \Theta (N^{3})} .

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: Além disso, não há necessidade de as matrizes serem quadradas. Matrizes não quadradas podem ser divididas ao meio usando os mesmos métodos, resultando em matrizes não quadradas menores. Se as matrizes forem suficientemente não quadradas, valerá a pena reduzir a operação inicial a produtos mais quadrados, usando métodos simples que são essencialmente O ( n 2 ) {\displaystyle O(n^{2})} , por exemplo: