BARTOLO LUQUE – Cuando multiplicamos dos matrices cuadradas A y B de N filas y N columnas (lo que en lenguaje de matrices llamamos «de orden N»), cada uno de los NxN elementos de la matriz resultante proviene del producto escalar de una fila de A con una columna de B. Algorítmicamente realizamos N productos y sumamos N números para obtener una entrada de la nueva matriz resultante. Los matemáticos dicen que el orden de complejidad de esa operación es O(N). Como debemos realizar N×N = N2 operaciones como esta, la matriz producto tiene un coste de O(N3).
¿Qué significa esto a nivel práctico? Supongamos que un programa de ordenador multiplica dos matrices de 1000 x 1000, con este algoritmo clásico, en T unidades de tiempo. Entonces, podemos esperar que si multiplicamos dos matrices de 2000 x 2000, el tiempo de ejecución se incremente 23 = 8 veces. El tiempo de ejecución crece con el cubo del tamaño N de la matriz.
Hasta 1969 se pensaba que este sería realmente el orden de complejidad del producto de matrices. Pero el profesor alemán Volker Strassen, para sorpresa de todos, corrigió este límite al proponer un algoritmo capaz de rebajar la complejidad hasta O(N2,807). Siguiendo con nuestro ejemplo anterior, al doblar el tamaño de la matriz, con el algoritmo de Strassen tardaríamos 22,807 = 6,998… veces más y no 8, como en el algoritmo clásico. Se abrió así la búsqueda de nuevas mejoras que parecieron culminar con el algoritmo de Coppersmith-Winograd en 1990, que estableció un límite práctico en O(N2,376), que se ha mantenido durante más de 20 años y que se explica desde entonces en cursos universitarios. (Redundando en nuestro ejemplo: 22,376 = 5,190…)
Virginia Vassilevska Williams
Sin embargo, el año pasado, el estudiante doctoral Andrew Stothers logró rebajar todavía más ese límite que parecía el definitivo. Lo rebajó de O(N2,376) a O(N2,374). Sorprendentemente el logro pasó desapercibido a la comunidad matemática porque su autor no publicó el resultado fuera de su tesis doctoral y dejó la matemática para dedicarse a la empresa privada. De hecho, ni siquiera se hacía mención del mismo en el resumen de resultados importantes de la tesis, como si Stothers y su director de tesis no fueran conscientes de la importancia del resultado. El logro se ha conocido fianalmente gracias a la estudiante postdoctoral Virginia Vassilevska Williams, que este pasado 28 de noviembre, ha propuesto un nuevo método con nueva rebaja a O(N2,3727).
La mejora desde el record de 1990 al nuevo de 2011 (pasando de exponente 2,376 a 2,3727) puede parecer ridícula, y vista desde fuera, el revuelo entre los expertos puede resultar incomprensible. Pero recordemos que el producto de matrices gigantescas y densas está al orden del día en aplicaciones que van desde la física nuclear a los mercados financieros, y cuando se trabaja con matrices de millones de elementos, el tiempo de cómputo no es despreciable (en nuestro ejemplo pasaríamos de 22,376 = 5,190… a 22,3727 = 5,179… veces más tiempo de ejecución al doblar el tamaño de la matriz). Sin olvidar que el nuevo descubrimiento vuelve a abrir la veda y la propia Virgina Vassilevska no ve descabellada la posibilidad de alcanzar un límite mínimo de complejidad de orden O(N2).
© 2012 Conec. Todos los derechos reservados.
No comments yet.