Estructuras de Datos y Algoritmos (EDA)

La Algoritmia persigue continuamente soluciones mejores para problemas conocidos. Uno de ellos es la multiplicación de matrices.

• El algoritmo estándar (basado en la aplicación directa de la definición del producto de matrices) requiere O(N³) operaciones aritméticas (sumas y multiplicaciones), para multiplicar matrices N x N.
• Es muy sencillo reducir ese coste a O(N^2,807), con un algoritmo de “divide y vencerás”, el algoritmo de Strassen (véase wikipedia o transparencias de “divide y vencerás” de la asignatura de Esquemas Algorítmicos).
• Durante veinte años, el algoritmo conocido con menor coste asintótico ha sido el de Coppersmith y Winograd, que requiere O(N^2,376).
• El año pasado, en su tesis doctoral, Andy Stothers propuso un algoritmo con coste asintótico O(N^2,374).
• Justamente ayer Virginia Vassilevska Williams dio a conocer la solución más rápida conocida hasta el momento, con un coste O(N^2,373).