¿Evidencia de que la multiplicación de matrices se puede hacer en tiempo cuadrático?

Se conjetura ampliamente que , el exponente óptimo para la multiplicación de matrices, es de hecho igual a 2. Mi pregunta es simple:$\omega$

¿Qué razones tenemos para creer que ?$\omega = 2$

Conozco algoritmos rápidos como Coppersmith-Winograd, pero no sé por qué estos podrían considerarse evidencia de .$\omega = 2$

Ingenuamente, me parece un ejemplo clásico en el que una comunidad solo espera que un resultado sea verdadero por razones estéticas. Me encantaría saber si ese es esencialmente el caso aquí.

Me gustaría agregar al comentario de Mark Reitblatt y la respuesta de Amir Shpilka. Primero, una de las conjeturas presentadas por Cohn, Kleinberg, Szegedy y Umans no es de teoría de grupos, sino puramente combinatoria (Conj. 3.4 en su documento FOCS '05 ). Esta conjetura dice que la "fuerte capacidad de USP es ". Coppersmith y Winograd, al exhibir su mejor algoritmo actual para la multiplicación de matrices, mostraron que la capacidad de USP es este mismo número (aunque no lo expresaron de esta manera). Aunque existe una diferencia entre los USP fuertes y los USP, esta es una evidencia de que su conjetura es al menos plausible.$\frac{3}{2^{2/3}}$$\frac{3}{2^{2/3}}$

(Para su otra Conjetura 4.7, que es teórica de grupo, no conozco ninguna evidencia similar de plausibilidad, más allá de la intuición).

En segundo lugar, estoy de acuerdo con Amir Shpilka en que la cadena de algoritmos pasados ​​tiene una sensación algo ad-hoc. Sin embargo, una de las cosas buenas del enfoque de teoría de grupos es que casi todos (no todos) los algoritmos anteriores pueden expresarse en este enfoque. Aunque las diversas construcciones teóricas grupales en [CKSU] pueden parecer un poco ad-hoc en el exterior, dentro del contexto del marco teórico grupal parecen significativamente más naturales y menos ad-hoc (al menos para mí) que muchos de ellos. Los algoritmos anteriores.

No sé acerca de los demás, pero puedo decirte por qué tiendo a creer que . Cuando lees la historia y el desarrollo de los algoritmos de multiplicación de matrices rápidas, creo que es difícil no sentir que todo lo que necesitamos es un algoritmo básico ligeramente mejor a partir del cual, incluso utilizando técnicas conocidas, seguirá . Básicamente, todos los algoritmos actuales (incluidos los de teoría de grupos) comienzan con una construcción "simple" que luego se amplifica. Esas construcciones son inteligentes, pero le dan al lector una especie de sentimiento "ad-hoc". No veo una razón para creer que no podemos llegar a mejores construcciones simples.ω = $\omega=2$$\omega=2$

Hay una analogía que uso para justificar la conjetura que para mí. Me doy cuenta de que esto es bastante heurístico, pero, sin embargo, me ha servido bien, por ejemplo, para comprender parte de la intuición detrás de Cohn et al. papel.$\omega = 2$

La convolución y la multiplicación de matrices son análogas. Si y son -by- matrices y , entonces . Si y son vectores de longitud y , entonces . En ambos casos, el resultado final es un vector que consiste en sumas de productos, pero la estructura relacional en los datos de entrada es diferente. Para convolución, podemos usar la FFT para calcular la respuesta en tiempo en lugar del trivial . Análogamente, uno podría esperar un$A$$B$$n$$n$$C = AB$$C(i,j) = \sum_{k=1}^n A(i,k) B(k,j)$$A$$B$$n$$C = A*B$$C(i) = \sum_{k=1}^n A(k)B(i-k)$O(n2) ˜ O (n2$\tilde{O}(n)$$O(n^2)$$\tilde{O}(n^2)$ algoritmo de tiempo para la multiplicación de matrices. La pregunta es: ¿cuál es el análogo de la transformada de Fourier que puede ayudar a la multiplicación de matrices?

Es más probable que sea . Tener parece fantástico ya que la contabilidad de factor constante no parece que pueda escalar.ω = $O(n^{2} log(n^2))$$\omega = 2$