Algoritmo de Coppersmith-Winograd

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de mayo de 2022; las comprobaciones requieren 8 ediciones .

El algoritmo de Coppersmith-Winograd es un algoritmo para multiplicar matrices cuadradas , propuesto en 1987 por D. Coppersmith y S. Winograd . En la versión original , la complejidad asintótica del algoritmo era , donde es el tamaño del lado de la matriz. El algoritmo de Coppersmith-Winograd, teniendo en cuenta una serie de mejoras y refinamientos en años posteriores, tiene las mejores asintóticas entre los algoritmos conocidos para la multiplicación de matrices. ${\ estilo de visualización O (n ^ {2.3755})}$ $norte$

En la práctica, el algoritmo de Coppersmith-Winograd no se usa, ya que tiene una constante de proporcionalidad muy grande y comienza a superar en velocidad a otros algoritmos conocidos solo para matrices cuyo tamaño excede la memoria de las computadoras modernas.

Mejoras en el algoritmo

En 2010, Andrew Stothers mejoró el algoritmo a [1] ${\ estilo de visualización O (n ^ {2.374}).}$
En 2011, Virginia Williams mejoró el algoritmo una vez más a [2] ${\ estilo de visualización O (n ^ {2.3728642}).}$
En 2014, Francois Le Gall simplificó el método de Williams y obtuvo una nueva estimación [3] ${\ estilo de visualización O (n ^ {2.3728639}).}$
En 2020, Josh Alman y Virginia Williams volvieron a mejorar el método alcanzando la partitura [4] ${\ estilo de visualización O (n ^ {2.3728596}).}$

Véase también

Algoritmo de Strassen
La hipótesis de Strassen
Problemas matemáticos abiertos : para determinar el límite inferior exacto de la complejidad del algoritmo de multiplicación de matrices.

Notas

↑ Stothers, Andrew (2010), Sobre la complejidad de la multiplicación de matrices , < https://www.era.lib.ed.ac.uk/handle/1842/4734 > Archivado el 29 de agosto de 2017 en Wayback Machine .
↑ Williams, Virginia (2011), Rompiendo la barrera de Coppersmith-Winograd. Archivado el 26 de octubre de 2014 en Wayback Machine .
↑ "Incluso si alguien logra probar una de las conjeturas, demostrando así que ω = 2, es poco probable que el enfoque del producto corona sea aplicable a los grandes problemas de matriz que surgen en la práctica. (…) las matrices de entrada deben ser astronómicamente grandes para que la diferencia de tiempo sea evidente”. Le Gall, François (2014), Powers of tensors and fast matrix multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation ( ISSAC 2014)
↑ Revista Cuanta

Literatura

Henry Cohn, Robert Kleinberg, Balazs Szegedy y Chris Umans. Algoritmos de teoría de grupos para la multiplicación de matrices. arXiv : matemáticas.GR/ 0511460 . Actas del 46º Simposio Anual sobre Fundamentos de Ciencias de la Computación , 23-25 de octubre de 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379-388.
Don Calderero y Shmuel Winograd . Multiplicación de matrices mediante progresiones aritméticas. Revista de Computación Simbólica , 9:251-280, 1990.
Robinson, Sara (2005), Hacia un algoritmo óptimo para la multiplicación de matrices , SIAM News Vol . 38 (9) , < http://www.siam.org/pdf/news/174.pdf > . Consultado el 20 de febrero de 2009. Archivado el 31 de marzo de 2010 en Wayback Machine .