Algoritmo de calderero-Winograd
El algoritmo Coppersmith-Winograd es un algoritmo para calcular el producto de dos matrices cuadradas de tamaño debido a Don Coppersmith y Shmuel Winograd en 1987 . Su complejidad algorítmica es lo que lo convierte en el algoritmo actual más asintóticamente eficiente. No hay indicios de que la complejidad sea óptima, y el exponente 2 generalmente se considera óptimo.
El algoritmo se utiliza como un bloque de construcción para probar los resultados teóricos sobre la complejidad algorítmica. Pero no se usa ninguna implementación del algoritmo porque la constante en la O grande es prohibitiva (es menos eficiente que la de Strassen en cualquier matriz que quepa en la memoria de una computadora actual).
El algoritmo Coppersmith-Winograd se encontró mediante métodos de representación de grupos finitos .
En su tesis, Andrew Stothers mejora el límite de la complejidad del algoritmo, mostrando que es inferior a 2,3737.
Ver también
Referencias
- Don Coppersmith y Shmuel Winograd . Multiplicación de matrices mediante progresiones aritméticas. Actas del XIX Simposio Anual de ACM sobre Teoría de la Computación , páginas 1 a 6, 1987.
- Sabemos que el exponente no puede ser menor que 2 ya que el algoritmo debe leer al menos las entradas de la matriz.
- Henry Cohn, Robert Kleinberg, Balazs Szegedy y Chris Umans. Algoritmos teóricos de grupos para la multiplicación de matrices. Actas del 46º Simposio Anual sobre Fundamentos de las Ciencias de la Computación , 23-25 de octubre de 2005, Pittsburgh, PA, IEEE Computer Society, págs. 379–388. Disponible en arXiv aquí .
- (en) Sobre la complejidad de la multiplicación de matrices (Capítulo 4) , Andrew James Stothers, PhD, Universidad de Edimburgo , 2010.
