Algoritmo de Strassen

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 (${\displaystyle O(n^{\log _{2}7})}$ versus ${\displaystyle O(n^{3})}$), 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.

Volker Strassen publicou este algoritmo pela primeira vez em 1969 e, assim, provou que o algoritmo de multiplicação de matrizes geral ${\displaystyle n^{3}}$ não era ótimo.^[1] 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 ${\displaystyle A}$, ${\displaystyle B}$ duas matrizes quadradas sobre um anel ${\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 ${\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 é, ${\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}$), mas isso é apenas conceitualmente necessário — se as matrizes ${\displaystyle A}$, ${\displaystyle B}$ não são do tipo ${\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 ${\displaystyle A}$, ${\displaystyle B}$ e ${\displaystyle C}$ em matrizes blocos de tamanhos iguais

${\displaystyle A={\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}},\quad C={\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}},\quad }$

com ${\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})}$. O algoritmo ingênuo seria:

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.}$

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 ${\displaystyle C_{ij}}$, 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:

${\displaystyle {\begin{aligned}M_{1}&=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\\M_{2}&=(A_{21}+A_{22}){\color {red}\times }B_{11};\\M_{3}&=A_{11}{\color {red}\times }(B_{12}-B_{22});\\M_{4}&=A_{22}{\color {red}\times }(B_{21}-B_{11});\\M_{5}&=(A_{11}+A_{12}){\color {red}\times }B_{22};\\M_{6}&=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\\M_{7}&=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\\end{aligned}}}$

usando apenas 7 multiplicações (uma para cada ${\displaystyle M_{k}}$) em vez de 8. Podemos agora expressar os ${\displaystyle C_{ij}}$ em termos de ${\displaystyle M_{k}}$:

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &M_{3}+M_{5}\\M_{2}+M_{4}\quad &M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.}$

Iteramos recursivamente este processo de divisão até que as submatrizes degenerem em números (elementos do anel ${\displaystyle {\mathcal {R}}}$). 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 ${\displaystyle A}$ e ${\displaystyle B}$, e estas serão então removidas neste ponto para obter a matriz ${\displaystyle C}$ (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.^[2] 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).^[3] Um estudo mais recente (2016) observou benefícios para matrizes tão pequenas quanto 512 e um benefício em torno de 20%.^[4]

É possível reduzir o número de adições de matrizes usando a seguinte forma descoberta por Winograd em 1971:^[5]

${\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 ${\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.^[6]

O algoritmo foi posteriormente otimizado em 2017 usando uma base alternativa,^[7] 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:^[8]

${\displaystyle {\begin{aligned}A_{22}&=A_{12}-A_{21}+A_{22};\\B_{22}&=B_{12}-B_{21}+B_{22},\end{aligned}}}$

${\displaystyle {\begin{aligned}C_{12}&=C_{12}-C_{22};\\C_{21}&=C_{22}-C_{21},\end{aligned}}}$

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

O número de adições e multiplicações necessárias no algoritmo de Strassen pode ser calculado como segue: seja ${\displaystyle f(n)}$ o número de operações para uma matriz ${\displaystyle 2^{n}\times 2^{n}}$. Então, pela aplicação recursiva do algoritmo de Strassen, vemos que ${\displaystyle f(n)=7f(n-1)+l4^{n}}$, para alguma constante ${\displaystyle l}$ que depende do número de adições realizadas em cada aplicação do algoritmo. Portanto, ${\displaystyle f(n)=(7+o(1))^{n}}$, ou seja, a complexidade assintótica para multiplicar matrizes de tamanho ${\displaystyle N=2^{n}}$ usando o algoritmo de Strassen é ${\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}$. 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,^[9] 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: ${\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})}$. A comparação desses dois algoritmos mostra que, assintoticamente, o algoritmo de Strassen é mais rápido: existe um tamanho ${\displaystyle N_{\text{threshold}}}$ 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 ${\displaystyle N_{\text{threshold}}}$ é tão grande que o algoritmo geralmente não é usado em matrizes que encontramos na prática.

Posto ou complexidade bilinear

[editar | editar código]

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 ${\displaystyle \phi$ :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C} } sobre um corpo F é definido como (um tanto quanto um abuso de notação)

${\displaystyle R(\phi /\mathbf {F} )=\min \left\{r\left|\exists f_{i}\in \mathbf {A} ^{*},g_{i}\in \mathbf {B} ^{*},w_{i}\in \mathbf {C} ,\forall \mathbf {a} \in \mathbf {A} ,\mathbf {b} \in \mathbf {B} ,\phi (\mathbf {a} ,\mathbf {b} )=\sum _{i=1}^{r}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}\right.\right\}}$

Em outras palavras, o posto de um mapa bilinear é o comprimento de seu cálculo bilinear mais curto.^[10] A existência do algoritmo de Strassen mostra que o posto da multiplicação de matrizes ${\displaystyle 2\times 2}$ 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
${\displaystyle i}$	${\displaystyle f_{i}(\mathbf {a} )}$	${\displaystyle g_{i}(\mathbf {b} )}$	${\displaystyle w_{i}}$		${\displaystyle f_{i}(\mathbf {a} )}$	${\displaystyle g_{i}(\mathbf {b} )}$	${\displaystyle w_{i}}$
1	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}}$
2	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&-1\end{bmatrix}}}$
3	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&1\end{bmatrix}}}$
4	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\1&0\end{bmatrix}}}$
5	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}-1&1\\0&0\end{bmatrix}}}$
6	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$
7	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$
8	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$
	${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}$				${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}$

Pode-se mostrar que o número total de multiplicações elementares ${\displaystyle L}$ necessárias para a multiplicação de matrizes está assintoticamente fortemente ligado ao posto ${\displaystyle R}$, isto é, ${\displaystyle L=\Theta (R)}$, ou mais especificamente, como as constantes são conhecidas, ${\displaystyle R/2\leq L\leq R}$. Uma propriedade útil do posto é que ele é submultiplicativo para produtos tensoriais, e isso permite mostrar que a multiplicação de matrizes ${\displaystyle 2^{n}\times 2^{n}\times 2^{n}}$ pode ser realizada com não mais que ${\displaystyle 7^{n}}$ multiplicações elementares para qualquer ${\displaystyle n}$. (Este produto tensorial ${\displaystyle n}$-vezes do mapa de multiplicação de matrizes ${\displaystyle 2\times 2\times 2}$ consigo mesmo — uma ${\displaystyle n}$-ésima potência tensorial — é realizado pela etapa recursiva no algoritmo mostrado.)

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;^[12] 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 ${\displaystyle O(n^{2})}$ em adições/subtrações; portanto, abaixo de um certo tamanho, será melhor usar a multiplicação convencional. Assim, por exemplo, uma matriz ${\displaystyle 1600\times 1600}$ não precisa ser preenchida para ${\displaystyle 2048\times 2048}$, pois poderia ser subdividida até matrizes ${\displaystyle 25\times 25}$ 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.^[3] 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 ${\displaystyle 199\times 199}$. Elas podem ser divididas de modo que a parte superior esquerda seja ${\displaystyle 100\times 100}$ e a inferior direita seja ${\displaystyle 99\times 99}$. Onde as operações exigirem, as dimensões de ${\displaystyle 99}$ são preenchidas com zero para ${\displaystyle 100}$ primeiro. Observe, por exemplo, que o produto ${\displaystyle M_{2}}$ é usado apenas na linha inferior da saída, portanto, é necessário apenas ter ${\displaystyle 99}$ linhas de altura; e assim o fator esquerdo ${\displaystyle A_{21}+A_{22}}$ usado para gerá-lo precisa ter apenas ${\displaystyle 99}$ linhas de altura; consequentemente, não há necessidade de preencher essa soma para ${\displaystyle 100}$ linhas; só é necessário preencher ${\displaystyle A_{22}}$ para ${\displaystyle 100}$ colunas para corresponder a ${\displaystyle A_{21}}$.

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 ${\displaystyle O(n^{2})}$, por exemplo:

• Um produto de tamanho ${\displaystyle [2N\times N]\ast [N\times 10N]}$ pode ser feito como 20 operações separadas ${\displaystyle [N\times N]\ast [N\times N]}$, arranjadas para formar o resultado;
• Um produto de tamanho ${\displaystyle [N\times 10N]\ast [10N\times N]}$ pode ser feito como 10 operações separadas ${\displaystyle [N\times N]\ast [N\times N]}$, somadas para formar o resultado.

Essas técnicas tornarão a implementação mais complicada, em comparação com simplesmente preencher para um quadrado de potência de dois; no entanto, é uma suposição razoável que qualquer pessoa que realize uma implementação de Strassen, em vez da multiplicação convencional, colocará uma prioridade maior na eficiência computacional do que na simplicidade da implementação.

Na prática, o algoritmo de Strassen pode ser implementado para alcançar melhor desempenho do que a multiplicação convencional mesmo para matrizes tão pequenas quanto ${\displaystyle 500\times 500}$, para matrizes que não são nada quadradas e sem exigir espaço de trabalho além dos buffers já necessários para uma multiplicação convencional de alto desempenho.^[4]

• Complexidade computacional de operações matemáticas
• Eliminação de Gauss-Jordan
• Complexidade computacional da multiplicação de matrizes
• Curva de ordem Z
• Algoritmo de Karatsuba, para multiplicar inteiros de n dígitos em ${\displaystyle O(n^{\log _{2}3})}$ em vez de ${\displaystyle O(n^{2})}$ tempo
  • Um algoritmo de multiplicação complexa semelhante multiplica dois números complexos usando 3 multiplicações reais em vez de 4
• Algoritmo de Toom-Cook, uma generalização mais rápida do algoritmo de Karatsuba que permite decomposição recursiva de dividir para conquistar em mais de 2 blocos de cada vez

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. Introduction to Algorithms, Segunda Edição. MIT Press e McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítulo 28: Seção 28.2: Strassen's algorithm for matrix multiplication, pp. 735–741.
• Knuth, Donald (1997). The Art of Computer Programming, Seminumerical Algorithms. II 3rd ed. [S.l.]: Addison-Wesley. ISBN 0-201-89684-2 

• Weisstein, Eric W. «Strassen's Formulas». MathWorld (em inglês)  (também inclui fórmulas para inversão de matriz rápida)
• Tyler J. Earnest, Strassen's Algorithm on the Cell Broadband Engine