O al menos es de un orden de magnitud.
Sólo he oído describirlo como "enorme", y en una búsqueda en Google no apareció nada.
Además, dado que el algoritmo de Strassen tiene una constante significativamente mayor que la de eliminación de Gauss, y que Coppersmith-Winograd es aún mayor, ¿hay algún indicio de qué constante podría tener un algoritmo de multiplicación de la matriz de O(n^2)?
En su segunda pregunta, creo que quiere decir "multiplicación de matriz ingenua", no "eliminación gaussiana".
Henry Cohn y otros tenían un lindo papel que relaciona los algoritmos de multiplicación de matrices rápidas con ciertos grupos. No hace mucho para responder a tu pregunta (a menos que quieras ir y probar los resultados conjeturados =), pero es una lectura divertida.
Además, para respaldar harrison No creo que nadie crea realmente que hay un $O(n^2)$ algoritmo. Un buen número de personas creen que es probable que haya un algoritmo que es $O(n^{2+ \epsilon })$ para cualquier $ \epsilon > 0$ . Un $O(n^2 \log n)$ el algoritmo encajaría en la cuenta.
editar: Se puede obtener una sensación de fondo para un límite inferior en el exponente de Coppersmith-Winograd basado en el hecho de que la gente no lo usa, incluso para n en el orden de 10.000; la multiplicación de la matriz ingenua requiere $2n^3 + O(n^2)$ fracasos, y Coppersmith-Winograd requiere $Cn^{2.376} + O(n^2)$ . Estableciendo las expresiones iguales y resolviendo para $C$ da que los dos algoritmos tendrían igual rendimiento para n = 10.000 (ignorando los patrones de acceso a la memoria, la eficiencia de la implementación y todo tipo de otras cosas) si la constante fuera alrededor de 627. En realidad, es probable que sea mucho mayor.
En respuesta a la segunda parte de su pregunta, creo que la sabiduría convencional es que hay no es un algoritmo O(n^2); de manera análoga al caso de la multiplicación de números enteros, no debería poder hacerlo mejor que sobre O(n^2 log n). (Raz ha demostrado que se trata de un límite inferior en el modelo de circuitos aritméticos con coeficientes limitados).
¿Cuál es la constante implícita allí? Probablemente sólo "enorme". Hasta donde sé, la razón por la que la gente cree que podemos lograr cerca de O(n^2) es básicamente por analogía con la multiplicación de números enteros, así que si quieres comprender las constantes, puede que valga la pena mirar las constantes en la multiplicación FFT.
Por cierto, ¿se ha publicado el volumen apropiado del Arte de la Programación de Computadoras, o lo será pronto? Sé que Knuth es muy exigente con la inclusión de este tipo de detalles, por lo que podría ser la referencia más obvia aparte del artículo original...
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
