Evidência de que a multiplicação de matrizes pode ser feita em tempo quadrático?

59

É amplamente suposto que , o expoente ideal para multiplicação de matrizes, é de fato igual a 2. Minha pergunta é simples:ω

Que razões temos para acreditar que ?ω=2

Conheço algoritmos rápidos como o Coppersmith-Winograd, mas não sei por que eles podem ser considerados evidências para .ω=2

Ingenuamente, parece-me um exemplo clássico em que uma comunidade apenas espera que um resultado seja verdadeiro puramente por razões estéticas. Gostaria muito de saber se esse é essencialmente o caso aqui.

Steve Flammia
fonte
12
Suspeito que a resposta seja em grande parte estética, e a falta de uma boa razão para ser maior que 2. Havia um artigo no FOCS '05 que dava algumas construções teóricas de grupo para a matriz mult que correspondiam aos expoentes conhecidos atuais e também forneciam 2 conjecturas teóricas de grupo que implicam . PDFω=2
Mark Reitblatt
5
Alguns anos atrás, tive uma conversa com Strassen, onde ele disse que acreditava em . Não sei ao certo quais foram as razões dele. ω>2
Ryan Williams
2
@ Ryan, vamos torcer para que Strassen leia cstheory.stackexchange. :)
Steve Flammia
3
Há um limite inferior de (sob algumas restrições) devido a Ran Raz; portanto, uma conjectura melhor seria que não é alcançado (mas o mínimo é de fato ). ω = 2 2Ω(nlogn)ω=22
Yuval Filmus
5
@Yuval, @Steve: 1) é geralmente definido como um limite. 2) Já sabemos que o que quer que seja , não é alcançado (é um inf e não um min). Veja este artigo da Coppersmith-Winograd: dx.doi.org/10.1137/0211038 . Do resumo: "o expoente para multiplicação de matrizes é um ponto limite, ou seja, não pode ser realizado por um único algoritmo". (Dado os detalhes de seus resultados, penso que esta declaração não consegue ser tomadas ingenuamente pelo valor de face, mas esta é principalmente uma questão técnica.)ωωω
Joshua Grochow

Respostas:

20

Gostaria de acrescentar ao comentário de Mark Reitblatt e à resposta de Amir Shpilka. Primeiro, uma das conjecturas apresentadas por Cohn, Kleinberg, Szegedy e Umans não é teórica de grupo, mas é puramente combinatória (Conj. 3.4 em seu artigo da FOCS '05 ). Essa conjectura diz que "a forte capacidade da USP é ". Coppersmith e Winograd, ao exibirem o melhor algoritmo atualmente para multiplicação de matrizes, mostraram que a capacidade da USP é esse mesmo número (embora eles não tenham expressado dessa maneira). Embora exista uma diferença entre USPs fortes e USPs, há alguma evidência de que sua conjectura é pelo menos plausível. 3322/3322/3

(Para a outra Conjectura 4.7, que é teórica em grupo, não conheço nenhuma evidência semelhante de plausibilidade, além da mera intuição.)

Segundo, concordo com Amir Shpilka de que a série de algoritmos passados ​​parece um pouco ad-hoc. No entanto, uma das coisas boas da abordagem da teoria dos grupos é que quase todos (não todos) os algoritmos anteriores podem ser expressos nessa abordagem. Embora as várias construções teóricas de grupos em [CKSU] possam parecer um pouco ad-hoc do lado de fora, dentro do contexto da estrutura teórica de grupos elas parecem significativamente mais naturais e menos ad-hoc (pelo menos para mim) do que muitas os algoritmos anteriores.

Joshua Grochow
fonte
Quando penso em Capacidade, penso em conjuntos e panelinhas independentes. Qual é o dicionário entre USPs e a construção explícita do gráfico subjacente e existe uma estrutura para esses gráficos?
T ....
28

Não conheço os outros, mas posso dizer por que acredito que . Quando você lê o histórico e o desenvolvimento de algoritmos de multiplicação de matriz rápida, acho que é difícil não sentir que tudo o que precisamos é apenas um algoritmo básico um pouco melhor a partir do qual, mesmo usando técnicas conhecidas, seguirá . Basicamente, todos os algoritmos atuais (incluindo os teóricos dos grupos) começam com alguma construção "simples" que é amplificada. Essas construções são inteligentes, mas dão ao leitor uma espécie de sentimento "ad-hoc". Não vejo uma razão para acreditar que não possamos criar construções simples melhores.ω = 2ω=2ω=2

Amir Shpilka
fonte
20

Existe uma analogia que eu uso para justificar a conjectura que para mim. Sei que isso é bastante heurístico, mas, no entanto, me serviu bem, por exemplo, para entender parte da intuição por trás de Cohn et al. papel.ω=2

Convolução e multiplicação de matrizes são análogas. Se e são por- matrizes e , então . Se e são vetores de comprimento e , então . Nos dois casos, o resultado final é um vetor que consiste em somas de produtos, mas a estrutura relacional nos dados de entrada é diferente. Para convolução, podemos usar a FFT para calcular a resposta em vez do trivial . Analogamente, pode-se esperar umaABnnC=ABC(i,j)=k=1nA(i,k)B(k,j)ABnC=ABC(i)=k=1nA(k)B(ik)S(n2) ~ S (n2)O~(n)O(n2)O~(n2) algoritmo de tempo para multiplicação de matrizes. A questão é: qual é o análogo da transformada de Fourier que pode ajudar na multiplicação da matriz?

arnab
fonte
-1

É mais provável que seja . Ter parece fantasioso, pois a contabilidade constante de fatores não parece escalável.ω = 2O(n2log(n2))ω=2

Chad Brewbaker
fonte
11
Você entende mal a definição de : é o menor de todos os modo que a multiplicação da matriz possa ser resolvida no tempo . Se houver um algoritmo de multiplicação de matriz , esse valor mínimo ainda será . BTW existe um ligado no modelo de circuitos aritméticos com coeficientes limitados. c O ( n c ) O ( n 2 log 10 n ) 2 Ω ( n 2 log n )ωcO(nc)O(n2log10n)2Ω(n2logn)
Sasho Nikolov
@SashoNikolov Obrigado por apontar isso. Alguém já tentou treinar uma rede neural para matemática booleana A * B = C? [Entradas A, B entradas, entradas C] -> Bool (multiplicação correta ou incorreta). Curioso que circuitos o gradiente decente / desistências traz; se os circuitos treinados tiverem atratores próximos das decomposições primárias. Em 3x3, 4x4, 5x5, 6x6, parece que uma hora de GPU daria alguns resultados interessantes.
Chad Brewbaker