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 é,

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

com

Então

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

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

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 é

.[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; Van Loan, Charles F. (1996). Matrix computations (em inglês) 3 ed. JHU Press [S.l.] pp. 31—33. ISBN 9780801854149. 


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