Algoritmo de Strassen

Em matemática, especificamente em álgebra linear, o algoritmo de Strassen, cujo nome é uma referência ao matemático Volker Strassen, seu criador, é um algoritmo utilizado para realizar a multiplicação de matrizes. Ele é assintoticamente mais rápido que o algoritmo tradicional, e é útil na prática ao lidar com matrizes grandes. Todavia ele é mais lento que o algoritmo mais veloz conhecido para a multiplicação de matrizes extremamente grandes. ^{[carece de fontes]}

História

Volker Strassen publicou o algoritmo de Strassen em 1969. Apesar de seu algoritmo ser apenas um pouco mais rápido do que o método padrão para a multiplicação de matrizes, ele foi o primeiro a observar que a abordagem usual não é ótima. Seu artigo iniciou a busca por algoritmos ainda mais rápidos tais como o algoritmo de Coppersmith-Winograd, que é mais complexo e foi publicado em 1987.

Algoritmo

Sejam A e B matrizes quadradas sobre um anel R e seja C o produto dessas matrizes, isto é,

$\mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in R^{2^{n}\times 2^{n}}.$

Para calcular esse produto, caso as matrizes A e B não sejam de ordem 2ⁿ x 2ⁿ, deve-se preencher com zeros as linhas e colunas restantes.

Particiona-se A, B e C em matrizes em blocos de mesmo tamanho

$\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1,1}&\mathbf {A} _{1,2}\\\mathbf {A} _{2,1}&\mathbf {A} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {B} ={\begin{bmatrix}\mathbf {B} _{1,1}&\mathbf {B} _{1,2}\\\mathbf {B} _{2,1}&\mathbf {B} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {C} ={\begin{bmatrix}\mathbf {C} _{1,1}&\mathbf {C} _{1,2}\\\mathbf {C} _{2,1}&\mathbf {C} _{2,2}\end{bmatrix}}$

com

$\mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in R^{2^{n-1}\times 2^{n-1}}.$

Então

$\mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}$

$\mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}$

$\mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}$

$\mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}$

Com essa construção, não houve qualquer redução no número de multiplicações. Continuam sendo necessárias 8 multiplicações para calcular as matrizes C_i,j, que é a mesma quantidade necessária para realizar a multiplicação de matrizes da forma usual.

Definem-se então as matrizes

$\mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})$

$\mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}$

$\mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})$

$\mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})$

$\mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}$

$\mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})$

$\mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})$

que serão então usadas para expressar os C_i,j em termos dos M_k. Devido a definição dos M_k pode-se eliminar uma multiplicação de matrizes e reduzir para 7 a sua quantidade (uma multiplicação para cada M_k) e expressar os C_i,j como

$\mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}$

$\mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}$

$\mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}$

$\mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}$

Faz-se a iteração deste processo de divisão n vezes até que as submatrizes se reduzam a números (elementos do anel R).

Em implementações práticas do método de Strassen, a multiplicação das submatrizes suficientemente pequenas é feita da forma usual, pois nesses casos ela é mais eficiente. O ponto exato em que o algoritmo de Strassen passa a ser mais eficiente depende da implementação específica e do hardware utilizado.

Complexidade assintótica

A multiplicação usual de matrizes exige aproximadamente 2N³ (em que N = 2ⁿ) operações aritméticas (adições e multiplicações), de modo que sua complexidade assintótica é O(N³).

No caso do algoritmo de Strassen, o número de adições e multiplicações necessárias pode ser calculado como segue: seja f(n) o número de operações para uma matriz 2ⁿ × 2ⁿ. Então, por meio de uma aplicação recursiva do algoritmo de Strassen, resulta que f(n) = 7f(n-1) + l4ⁿ, para alguma constante l que depende do número de adições executadas a cada aplicação do algoritmo. Assim, f(n) = (7 + o(1))ⁿ, ou seja, a complexidade assintótica da multiplicação de matrizes de tamanho N = 2ⁿ por meio do método de Strassen é

$O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.807})$.

No entanto, a redução no número de operações aritméticas vem ao preço de uma estabilidade numérica um pouco reduzida.

Referências

• Golub, Gene Howard; Van Loan, Charles F. (1996). Matrix computations (em inglês) 3 ed. [S.l.]: JHU Press. pp. 31—33. ISBN 9780801854149