Sorprendentes historias personales tras "bombazo" inesperado en investigación de multiplicación matricial: O(Nω), ω <2,3727

Una noticia inesperada irrumpió el pasado lunes en el tranquilo mundo del álgebra lineal, en un área concreta donde ya casi todos pensaban (pensabamos) que estaba todo inventado.

La historia completa incluye pésimos directores de tesis, redescubrimientos independientes y a un brillante matemático que se olvida de publicar sus resultados por su trabajo como asesor financiero…

Virginia Vassilevska Williams, la investigadora postdoc en Berkeley y Stanford que ha dado la sorpresa esta semana.

Hasta 1969, el coste de multiplicar dos matrices de tamaño NxN se creía que estaba limitado al orden de complejidad ( O(N^3) ), como se desprende de un análisis naive del algoritmo de multiplicación:

Algoritmo estándar de multiplicación matricial (fuente)

Cada elemento (i,j) de la matriz resultante proviene de sumar el producto (escalar a escalar) de una fila de A con una columna de B. Si todas las matrices son de NxN, esto implica  (O(N) ) operaciones, por cada una de las  (N times N=N^2) entradas de la matriz producto, nos da el obvio  (O(N^3)).

Los matemáticos vivieron felices con esta idea como decía, hasta 1969, cuando el profesor alemán Volker Strassen anunció un gran descubrimiento: el límite de complejidad cúbica no era imbatible. Su nuevo algoritmo consiguió rebajar la complejidad hasta (O(N^{2,807})).

En valores absolutos, no hay mucha diferencia entre un exponente 3 y 2,807, pero la relevancia de su descubrimiento fue, sencillamente, que ahí había campo para investigar y mejorar.

A partir de su artículo de 1969, se abrió la búsqueda de nuevos algoritmos, y así se llegó en 1990 al que ha sido el mejor método durante 20 años: el algoritmo de Winograd (PDF).

Su complejidad de ( O(N^{2,376}) ) se mantuvo imbatible durante largos años, convirtiéndose casi en un límite «óptimo» de facto del que parecía nadie iba a ser capaz de pasar para productos de matrices cuadradas genéricas. El número 2,376 se ha enseñado durante dos décadas en las universidades como «el límite».

Pero los cambios se suceden con velocidad «vertiginosa» ultimamente, al menos si lo comparamos con el parón de 20 años.

El año pasado, Andrew Stothers introdujo en su tesis (PDF) el primer avance en 20 años, rebajando el límite de 2,376 a 2,374.

Pero nadie se enteró.

Aparentemente mal aconsejado por su entorno (¿director de tesis, departamento?), apenas mencionó el importante descubrimiento como contribución de su tesis, y sólo se menciona al llegar a la página 81. Incomprensiblemente, ¡ni siquiera menciona este hecho en el abstract de la tesis!

Dice que pretendía haber escrito un paper detallando su nuevo algoritmo, pero entre la salud y el trabajo (asesor de riesgo financiero en el Royal Bank of Scotland…), se acabó liando y nunca lo llegó a publicar (WTF!!!).

Lo más alucinante de todo es que explica en su perfil de LinkedIn que gracias a la tesis:

«Investigé mejoras en el tiempo de multiplicar matrices […] y con esa experiencia mejoré mis habilidades con Word, Excel, …»

¡En serio, este hombre se merece un premio! Como dice Scott Aaronson, quien ayer sacó toda esta historia a la luz, esa subrealista surrealista mención a Word y Excel le inmortalizará en los anales del folklore matemático.

Bien, esa es la primera parte de la historia, recordad, desconocida en todo su alcance hasta ayer.

En ese contexto, el anuncio el lunes 28 de noviembre por parte de Virginia de su nuevo método con complejidad w<2,3727 se puede entender que organizase un revuelo por ser el primer avance en 20 años en un tema con grandes aplicaciones prácticas para el producto de matrices (densas, las dispersas se investigan por otro lado) de enorme tamaño.

En su paper publicado el lunes (PDF) explica el porqué (en su opinión) de ese vacío de 20 años. Aconsejo al lector técnico que lo lea él mismo, pero resumido: la solución alcanzada en 1990 señalaba una dirección, y al adentrarse un poco más en ese camino nadie vio mejora alguna… hasta que Virginia consiguió adentrarse no un poco, sino mucho más en esa dirección. Ese camino era muy complejo, pero ha dado sus frutos.

La mejora desde el record de 1990 al nuevo de 2011 (desde 2,376 hasta 2,3727) puede parecer ridículo, pero cuando se trabaja con matrices de millones de elementos, cualquier mejora es importantísima. Además, hablamos de exponentes de órdenes de complejidad, con lo que las mejoras son cada vez más relevantes conforme trabajamos con matrices mayores.

Por cierto, el trabajo de Andrew en 2010 parece haberse puesto a la luz pública gracias a este último trabajo de Virginia, ya que emplea algunas de sus ideas, si bien tiene el mérito de llegar a una solución independiente.

Curiosamente, la investigadora menciona ciertas conjeturas de otros matemáticos que, de ser ciertas, podrían llevar a un límite mínimo de complejidad ( O(N^2) ), muy lejos del último descubrimiento. Si bien, esas conjeturas podrían no ser válidas. Hoy, la cuestión es un tema abierto.

Y para concluir esta extraña narración, menciono como curiosidad que Virginia avisa en su web que se le acaba el contrato este curso y busca a quien la contrate…

Esperemos que su último trabajo le ayude en su búsqueda, estoy seguro de que se lo merece.

Personalmente, agradezco a jafma haberme hecho llegar esta agradable noticia 😉