Algoritmo de Strassen

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 2n x 2n, 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 Ci,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 Ci,j em termos dos Mk. Devido a definição dos Mk pode-se eliminar uma multiplicação de matrizes e reduzir para 7 a sua quantidade (uma multiplicação para cada Mk) e expressar os Ci,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.[1] 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[editar | editar código-fonte]

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

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 2n × 2n. Então, por meio de uma aplicação recursiva do algoritmo de Strassen algorithm, resulta que f(n) = 7f(n-1) + l4n, 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))n, ou seja, a complexidade assintótica da multiplicação de matrizes de tamanho N = 2n por meio do método de Strassen é

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

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.

Notas[editar | editar código-fonte]

  1. Golub (1996), p. 32.
  2. Golub (1996), p. 33.

Referências[editar | editar código-fonte]

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


Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.