É 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 ?
Conheço algoritmos rápidos como o Coppersmith-Winograd, mas não sei por que eles podem ser considerados evidências para .
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.
ds.algorithms
linear-algebra
matrix-product
Steve Flammia
fonte
fonte
Respostas:
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/3 322/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.
fonte
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
fonte
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 umaA B n n C=AB C(i,j)=∑nk=1A(i,k)B(k,j) A B n C=A∗B C(i)=∑nk=1A(k)B(i−k) 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?
fonte
É mais provável que seja . Ter parece fantasioso, pois a contabilidade constante de fatores não parece escalável.ω = 2O(n2log(n2)) ω=2
fonte