Antecedentes: El Algoritmo de Strassen, que se describe aquí, tiene una complejidad computacional de $\text{O}(n^{2.807})$ para la multiplicación de dos $n \times n$ matrices (el exponente es $\frac{\log7}{\log2}$). Sin embargo, la constante es tan grande que este algoritmo es de hecho más lento en la práctica que el ingenuo de la multiplicación de la matriz para las pequeñas $n$. Del mismo modo, el Calderero-Winograd algoritmo, que tiene la menor complejidad asintótica de todos los conocidos algoritmos de la multiplicación de la matriz, tiene un exponente de $2.376$ y se discutió aquí anteriormente.
Pregunta: Recientemente, hice un reclamo en un documento entregado que el de Smith de forma normal algoritmo tiene super-cúbico de complejidad y un revisor replicó diciendo que, en realidad, la complejidad se ha reducido a la multiplicación de la matriz de tiempo = $n^{2.37\ldots}$. Yo no soy un experto en la matriz de algoritmos y volvería a cambiar la línea incorrecta, pero la experiencia me ha obligado a preguntarse, ¿cuáles son las implicaciones prácticas de decir "X se puede hacer en la multiplicación de la matriz de tiempo"? Más precisamente,
¿Existe una real implementación de software de Calderero Winograd? Si no, hay un obstáculo teórico para su existencia?
Por un teórico obstáculo no me refiero a algo como "Bien, sería mejor que las técnicas existentes para $n$ más grande que el número de átomos en el universo ¿cuál es el punto?", sino más bien algo así como "el algoritmo utiliza el axioma de elección, o la clasificación de los finitos simples grupos", etc.
PS: Bueno, por lo que también es este el papel que al parecer reduce la complejidad de la Calderero-Winograd enfoque a $2.3737$ de $2.376$, por lo que acepto la corrección acerca de CW ser el más rápido. La pregunta sigue en pie, si reemplazamos la CW por el método de V. V. Williams.
