/fdata%2F4067159%2Favatar-blog-1187481218-tmpphpXnuMXO.jpeg){kind=avatar}
actualidad
Bombazo inesperado
Sorprendentes historias personales tras "bombazo" inesperado en investigación de multiplicación matricial: O(Nω), ω <2,3727
Una noticia inesperada ha irrumpido en el tranquilo mundo del álgebra lineal, en un área concreta donde ya casi todos pensaban 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...
Hasta 1969, el coste de multiplicar dos matrices de tamaño NxN se creía que estaba limitado al orden de complejidad O(N3), como se desprende de un análisis naive del algoritmo de multiplicación:
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×N=N2 entradas de la matriz producto, nos da el obvio O(N3).
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(N2,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 .
Su complejidad de O(N2,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.
Andrew Stothers introdujo en su tesis 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 artículo 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
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 sacó toda esta historia a la luz, esa surrealista mención a Word y Excel le inmortalizará en los anales del folklore matemático.
En ese contexto, el anuncio el lunes 28 de noviembre de 2011 por parte de Virginia Vassilevska Willians , investigadora en Berkeley y Stanford, 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 artículo publicado el lunes 28 explica el porqué (en su opinión) de ese vacío de 20 años: 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(N2), muy lejos del último descubrimiento. Si bien, esas conjeturas podrían no ser válidas. Hoy, la cuestión es un tema abierto.
Mencionar 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, seguro de que se lo merece.
Ciencia explicada
