Multiplicar dos matrices cuadradas densas, cuyo número de elementos es O(n2), por el algoritmo convencional requiere un coste computacional de O(n3), sin embargo, se conocen algoritmos con un coste de O(n2+ε), con ε<1.
Virginia Vassilevska Williams ha logrado el récord hasta hoy con ε=0,3737, superando por poquito el anterior récord de Coppersmith y Winograd
de ε=0,376. ¡Increíble!
El artículo técnico es Virginia Vassilevska Williams (UC Berkeley and Stanford University), “Breaking the Coppersmith-Winograd barrier,” como nos cuenta Jacob Aron, “Key mathematical tool sees first advance in 24 years,”
El primer algoritmo que bajó de ε=1 fue descubierto en 1969,
por Strassen que logró alcanzar ε=0,808 para el costo en tiempo de ejecución del algoritmo.
Desde entonces muchos matemáticos han intentado que su nombre
pase a la historia aplicando mucha imaginación a este problema.
En 1978, Pan logró ε=0,796 y pronto Bini et al. lo bajaron a ε=0,78.
Un gran salto fue obtenido en 1981 por Schönhage que logró ε=0,548;
que en poco tiempo logró reducir a ε=0,522, y luego en 1982 Romani
alcanzó ε=0,517.
La barrera de ε=0,5 fue superada gracias a Coppersmith y Winograd
que obtuvieron ε=0,496.
En 1986, Strassen lo bajó a ε=0,479. Y finalmente en 19889,
de nuevo Coppersmith y Winograd obtuvieron su famoso ε=0,376.
Resultado que ha resistido 24 años durante los cuales se han obtenido varios algoritmos con ε=0,376, como el de Kleinberg y Szegedy de 2005.
Muchos pensaban que sería difícil bajar esta cifra, aunque Coppersmith
y Winograd, y Cohn et al. conjeturaron que sería posible llegar a ε=0.
¿Será posible?
Quien sabe, pero el trabajo de Williams es todo un gran descubrimiento matemático.
¿Cómo ha logrado Williams obtener el algoritmo
más rápido que existe
(hasta ahora)?
No sorprenderá a muchos pues lo ha logrado analizando en extremo detalle
el algoritmo de Coppersmith y Winograd.
Gracias a dicho análisis ha notado que un resquicio que dejaron abierto
sus autores, la posibilidad de que utilizando la octava potencia del algoritmo desarrollado por ellos pudiera mejorar ligeramente el tiempo de cómputo.
Williams ha demostrado que su intuición era correcta y gracias a un esfuerzo hercúleo ha logrado la mejora que pone su nombre en la historia
de las matemáticas.
¿Cómo funciona el algoritmo?
Les pido perdón pero no lo voy a tratar de explicar.
Quien conozca el algoritmo de Coppersmith y Winograd puede leer directamente el artículo de Williams sin más (la idea está bastante clara aunque los detalles son engorrosos).
Quien no lo conozca debería estudiarlo primero;
yo empezaría por el algoritmo de Strassen.
Muy brevemente la idea de estos algoritmos es muy similar a la idea
de la transformada rápida de Fourier (FFT), una técnica divide y vencerás binaria que parte el problema de tamaño n en subproblemas más sencillos
de tamaño n/2; como en el caso de la FFT la versión “fácil” de estos algoritmos requiere que las matrices tengan un tamaño n
que sea potencia de 2.
No hay comentarios:
Publicar un comentario