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 é,
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
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, 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
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
![]() | Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
|