Gran descubrimiento matemático: El algoritmo de multiplicación de matrices más rápido que existe

Por Francisco R. Villatoro, el 9 diciembre, 2011. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Noticias • Science ✎ 10

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,» New Scientist, 09 Dec. 2011.

El primer algoritmo que bajó de ε=1 fue descubierto en 1969, por Strassen que logró alcanzar ε=0,808 para el coste 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? Os 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.



10 Comentarios

  1. Es fantástico, sobre todo porque el coste cuadrático es «engañoso» (n^2 proviene de los datos del problema, no de la solución a dicho problema), vaya, que el algoritmo tiene coste «casi» lineal.

  2. Javier, tienes razón, lo de «gran descubrimiento» es sensacionalista, pero como yo trabajo en estos asuntos me he dejado llevar por la emoción.

    En cuanto a Burkhard Heim, trataré de dedicarle un post, pero como sus trabajos están escritos en alemán tengo que buscar traducciones (y la web de su grupo no están por la labor, no sé el porqué).

  3. Me congratula lo que para mí sí es un gran avance, en lo conceptual y en aplicaciones que afectarán a todo el mundo. Mi enhorabuena a la descubridora.

    1. Leo, no entiendo la pregunta. La convolución entre dos vectores es lo mismo que un producto de matrices de Toeplitz, pero el producto de matrices y las convoluciones son cosas diferentes. Recuerda que el coste de la convolución de dos vectores es como muy mucho O(n log(n)) usando FFT. No sé, quizás mi respuesta está ida de olla… realmente no entiendo tu pregunta.

    2. La terminología «producto de convolución» tal y como la he encontrado en un artículo personal de Wikipedia da lugar a engaño [http://es.wikipedia.org/wiki/Usuario:MRS/producto_de_convoluci%C3%B3n].
      Leo, la operación lineal de convolución se refiere al operador que te indica Francis, y es utilizado en los campos a los que haces referencia cuando la transformación es espacialmente invariante. En su versión discreta puede ser implementado eficientemente mediante transformadas de Fourier como te decía Francis (ya que los autovectores de las matrices Toeplitz coinciden con los vectores de la base de Fourier).

      1. Multiplication and the convolution product pp.162-209.
        The Theory of Generalised Functions; D.S. Jones. Cambridge University Press, 1982

        The convolution product pp. 254-258
        Differential Equations An Introduction to Basic Concepts, Results and Applications; Ioan Vrabie. World Scientific Publishing Co, 2004

        Salu2

  4. «Un gran descubrimiento matemático es plantear una conjetura, o resolverla.

    Pero crear un algoritmo que reduzca en un 20%, 50%, o incluso 80% el numero de operaciones precisas, bueno, puede tener buenas aplicaciones tecnológicas (Codificadores mejores), pero no resuelve ni plantea nada nuevo en matemáticas».

    Completamente en desacuerdo y cualquiera que haya trabajado en algrítmica lo sabe. Un algoritmo puede ser perfectamente un gran descubrimiento matematico. Esto no es lo mismo que afirmar que este lo sea, pues en realidad no es práctico (para mi esto cuenta, quizás no para otros). Hay un trade-off entre reducir el exponente y aumentar la constante oculta en la notación Big O.

    Pero llueve sobre mojado: puedes ver las discusiones sobre esto en los blogs Computational Complexity (http://blog.computationalcomplexity.org/2011/12/what-is-breakthrough.html), Godel Lost letter (http://rjlipton.wordpress.com/2011/11/29/a-breakthrough-on-matrix-product/) o Shtetl-optimized (http://www.scottaaronson.com/blog/?p=839).

  5. Hola Javier,

    Gracias por tu comentario.

    En mi opinión (estoy de acuerdo que todo esto es materia opinable) en ambos tipos de algoritmos, según tu clasificación, podemos encontrar grandes resultados matemáticos. Según y cómo.

    Por ejemplo, un algoritmo del primer tipo que resolviese un problema NP-completo en tiempo lineal sería utilizando una combinación de herramientas ya conocidas sería considerado cómo tal (ejemplo posiblemente poco realista). En general, espectaculares ganancias en la eficiencia (a veces incluso si solo es teórica) de resolución de problemas ya conocidos pueden considerarse grandes resultados.

Deja un comentario