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

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.

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

  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. Hombre, lo de ‘Gran Descubrimiento matemático’, vaya, no lo veo muy acertado.

    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.

    No es nada facil, lo sé, hay que jugar con todas las dimensiones de nuestras neuronas para logarlo.

    Pero no es un gran descubrimiento matematico.

    Un gran descubrimiento matemático fue la transformada de Laplace, o la de Fourrier.

    Pero la FFT (Fast Fourrier Transformate), es solo una herramienta útil.

    Tremendamente util, si quieres, pero una herramienta, no un descubrimiento.

    O lo que Euler dejó en su lapida: exp(j·x)….= cos(x)..+j·sin(x)…

    Eso si que son descubrimientos matemáticos.

    O las geometrías de Rienman.

    Vamos, es mi opinión.

    Saludos.

    Y buen F.D.S.

    (Please Francisco, mírate lo que te he dicho hace dos comentarios, un post sobre Burkhard Heim).

    • 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é).

      • “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. ”

        No te eches para abajo francisco.

        Que ya nos contaste que después de informática, te curraste físicas.

        Y esto no te da un duro (Salvo los eurillos del CPAN, cuatro perrillas tal como está la vida).

        Al contrario, mas de un disgusto.

        Gracias por tu trabajo , gracias.

  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.

    • 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.

      • Producto de convolución de dos funciones matriciales, muy utilizado en el procesamiento digital de imágenes, radioastronomía o en control de sistemas. Salu2

    • 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).

      • 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).

    • Proanuiq,

      Hay dos clases de algoritmos, al menos.

      A).- Los que resuelven una operación matemática.
      Éste, es un ejemplo.
      Los de Levinson-Durbi, para resolver sistemas lineales con matrices de Toeplitz, es decir, para resolver sistemas de autocorrelacion (Que no correlacion en generla, donde no salen matrices de Toeplitz), otros.

      El viejo algoritmo de Newton para integrar numéricamente, otro.

      B)..- Los que crean algo nuevo.
      Los algoritmos adaptativos, por ejemplo, en sus infiitas variedades.

      |—————————————-|

      Hacer uno del primer tipo, puede cambiar todo un mundo técnico, o científico, pues da una herramienta sin la cual es imposible, por ejemplo, sistemas de telefonía mobil, o procesar en tiempo real la información de los billones de colisiones del sistema de Trigger del LHC.

      O aterrizar-despegar aviones de decenas de toneladas, como el Airbus-335.

      Son herramientas maravillosas qe hacen posible nuevas funciones que nunca podrian salir sin ellos.

      Hacer uno del 2º tipo,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Igual y mas.

      Y en cuanto a dificultad, Proanuiq, crear el concepto de Transformada de Laplace, dudo que requiriera menos esfuerzo mental o brillantez que algoritmos como los de L.P.C. (Linear Predictive codding).

      En todo eso, importancia (practica y para abrir campos científicos), y dificultad en su consecución. estoy de acuerdo contigo.

      Pero , personalmente, para mi, el primer tipo, solo son herramientas.

      El 2º tipo de algoritmos, para mi, si pertenece a esa otra categoría de ‘creación’ que si merece el calificativo de gran descubrimiento.

      Ciertamente, ‘llueve sobre mojado’, este tipo de discusiones son típicas de matemáticas.

      Por eso quiero fijar, esto es solo mi opinión.

      Saludos.

  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.

Los comentarios están cerrados.