Algoritmo de Strassen
# 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. $^[$

## 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$^n$ x 2$^n$, 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$^3$ (em que N = 2$^n$) operações aritméticas (adições e multiplicações), de modo que sua complexidade assintótica é O(N$^3$).
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$^n$ × 2$^n$. Então, por meio de uma aplicação recursiva do algoritmo de Strassen, resulta que f(n) = 7f(n-1) + l4$^n$, 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 = 2$^n$ 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.