Como Strassen apresentou seu método de multiplicação de matrizes?

O famoso algoritmo de multiplicação de matrizes de Strassen é um verdadeiro deleite para nós, pois reduz a complexidade de tempo do O (n ³ ) tradicional para O (n ^2,8 ).

Mas de todos os recursos pelos quais passei, até o livro de Cormen e Steven Skienna, eles claramente não afirmam como Strassen pensava sobre isso.

Qual é a lógica do algoritmo de multiplicação de matrizes de Strassen? É um acidente de sorte ou há algo mais profundo nele?

Além de Strassen, ninguém é capaz de lhe contar como Strassen teve sua ideia. No entanto, posso lhe dizer, como você poderia ter encontrado essa fórmula - desde que esteja interessado em geometria algébrica e teoria de representação. Isso também fornece as ferramentas para mostrar que a fórmula de Strassen é tão boa quanto possível, ou mais precisamente, que não existe uma fórmula que calcule o produto de duas matrizes 2 × 2 que usam menos de 7 multiplicações .

Como você está interessado em matrizes, presumo que você saiba álgebra linear básica e ficará um pouco confuso com os detalhes mais avançados.

Primeiro seja E o conjunto de todos os mapas lineares de um plano para um plano. Esse é basicamente o conjunto de todas as matrizes 2 × 2, mas esquecemos um sistema de coordenadas específico - porque, se houvesse um sistema de coordenadas melhor que o “padrão”, poderíamos ter interesse em usá-lo para multiplicação de matrizes. Também denotamos por E † o espaço duplo de E e por X = P (E⊗E † ⊗E †) o espaço projetivo associado ao produto tensorial E⊗E † ⊗E † .

Um elemento de X = P (E⊗E † ⊗E †) da forma especial [c⊗α⊗β] pode ser interpretado como uma operação elementar em matrizes que, em alguns sistemas de coordenadas apropriados, lê um coeficiente de uma matriz um e um coeficiente de uma matriz B e escreve o produto destes coeficientes de alguma matriz C . Um elemento geral de X é uma combinação destas operações elementares, de modo que o produto π de duas matrizes, entendida como um mapa de P (E) x P (E) a P (E), é um ponto em X .

A fórmula usual do produto da matriz e a fórmula de Strassen podem ser expressas como combinações dessas operações lineares, então deixe-me denotar por W₁ o conjunto dessas operações elementares [c⊗α⊗β] e deixe-me descrever geometricamente suas combinações.

Seja W₂ a variedade de secantes de W₁ em X. É obtido tomando-se (fechamento da) união de todas as linhas que passam por dois pontos (genéricos) de W₁ . Podemos pensar nisso como um conjunto de todas as combinações de duas operações elemetárias.

Seja W₃ a variedade de planos secantes de W2 em X. É obtido tomando-se (fechamento da) união de todos os planos passando por três pontos (genéricos) de W2 . Podemos pensar nisso como um conjunto de todas as combinações de três operações elemetárias.

Da mesma forma, definimos variedades secantes para índices maiores. Observe que essas variedades crescem cada vez maiores, ou seja, W₁⊂W₂⊂W₃⊂ ⋯ Portanto, a fórmula clássica do produto da matriz mostra que o produto das matrizes é um ponto de W₈ . Na realidade

PROPOSIÇÃO (Strassen) - O produto das matrizes π está em W₇.

Até onde eu sei, Strassen não colocou as coisas dessa maneira, no entanto, este é um ponto de vista geométrico sobre esta questão. Este ponto de vista é muito útil, porque também permite provar que a fórmula de Strassen é a melhor, ou seja, que π não está em W₆ . Os métodos geométricos desenvolvidos aqui também podem ser usados ​​para uma ampla gama de problemas.

Espero ter pego sua curiosidade. Você pode ir além, lendo este artigo de Landsberg e Manivel:

http://arxiv.org/abs/math/0601097

¹ Não vou consertar esse erro, porque peguei um resfriado.

Acabei de receber a tarefa de fazer isso na lição de casa e achei que tinha uma epifania perfeita: o algoritmo de Strassen sacrifica a "amplitude" de seus componentes de pré-soma para usar menos operações em troca de componentes de pré-soma "mais profundos" ainda pode ser usado para extrair a resposta final. (Esta não é a melhor maneira de dizer isso, mas é difícil para mim explicar).

Vou usar o exemplo da multiplicação de dois números complexos para ilustrar o saldo de " operações versus componentes ":

Observe que usamos 4 multiplicações, que resultam em 4 componentes do produto :

Observe que os dois componentes finais que queremos: as partes reais e imaginárias do número complexo são na verdade equações lineares: são somas de produtos em escala. Então, estamos lidando com duas operações aqui: adição e multiplicação.

O fato é que nossos 4 componentes do produto podem representar nossos 2 componentes finais se simplesmente adicionarmos ou subtrairmos nossos componentes:

Porém, nossos 2 componentes finais podem ser representados como somas de produtos. Aqui está o que eu vim com:

Se você pode ver, na verdade, precisamos apenas de 3 componentes de produtos distintos para fazer os dois últimos:

Mas espere! Cada uma das letras maiúsculas são em si produtos! Mas o problema é que sabemos que podemos gerar (A + B + C + D) a partir de (a + b) (c + d), que é apenas uma multiplicação.

Portanto, no final, nosso algoritmo é otimizado para usar componentes menos, mas mais "gordos", onde trocamos a quantidade de multiplicações por uma operação mais somatória.

Parte do que permite isso é a propriedade distributiva, que permite que A (B + C) seja equivalente a (AB + AC). Observe como o primeiro pode ser calculado usando 1 operação de adição e 1 multiplicação, enquanto o segundo requer 2 multiplicações e 1 soma.

O algoritmo de Strassen é uma extensão da otimização que aplicamos a produtos com números complexos, exceto que existem mais termos de produto-alvo e possivelmente mais componentes de produto que podemos usar para obtê-los. Para uma matriz 2x2, o algoritmo de Strassen transforma um algoritmo que precisa de 8 multiplicações para um que precisa de 7 multiplicações e aproveita a propriedade distributiva para "mesclar" duas multiplicações em uma operação e, em vez disso, tira o novo nó "mais gordo" para extrair uma. termo do produto ou outro, etc.

Um bom exemplo: para obter (-1) e (2) e (5), você pode pensar nisso como apenas (-1), (2), (5) ou como (2-3) ), (2), (2 + 3). As segundas operações usam números menos distintos, no entanto. O problema é que o número de números distintos é equivalente ao número de componentes do produto que você precisa calcular para a multiplicação da matriz. Simplesmente otimizamos para encontrar uma certa visão das operações subjacentes que aproveitam as saídas isomórficas usando uma variação diferente através da propriedade distributiva.

Talvez isso possa estar ligado à topologia de alguma forma? Esta é apenas a maneira de meu leigo entender isso.

Edit: Aqui está uma foto das minhas anotações que desenhei no processo de explicação complexa dos números: