Para los científicos computacionales y los matemáticos, las opiniones sobre el «exponente 2» se reducen a una sensación sobre cómo debería ser el mundo.
«Es difícil separar el pensamiento científico de las ilusiones», reconoce Chris Umans, del Instituto de Tecnología de California. «Quiero que el exponente sea 2 porque es hermoso.»
El «exponente 2» se refiere a la velocidad ideal (en términos del número de pasos requeridos) con que podría llevarse a cabo una de las operaciones más básicas de las matemáticas: el producto de matrices. Si el exponente 2 es alcanzable, entonces la multiplicación de matrices puede realizarse tan rápido como es materialmente posible. Si no lo es, estamos atrapados en un mundo que no se amolda a nuestros sueños.
Las matrices son conjuntos de números. Cuando tenemos dos matrices de tamaños compatibles, es posible multiplicarlas para generar una tercera matriz. Por ejemplo, si partimos de un par de matrices 2 × 2 («dos por dos», con dos filas y dos columnas), su producto también será una matriz 2 × 2, con 4 elementos. De modo más general, el producto de dos matrices n × n es otra matriz n × n con n2 elementos.
Por ese motivo, el mínimo número de pasos concebible a la hora de multiplicar dos matrices es n2, es decir, los que se necesitan simplemente para escribir la respuesta. De ahí es de donde viene el «exponente 2».
Y aunque nadie sabe con certeza si se puede alcanzar, los investigadores siguen dando pasos en esa dirección.
Un artículo publicado en octubre es el que más se ha acercado, al describir el método más rápido conocido hasta la fecha para multiplicar dos matrices. El resultado, obtenido por Josh Alman, investigador postdoctoral de la Universidad Harvard, y Virginia Vassilevska Williams, del Instituto de Tecnología de Massachusetts, reduce en aproximadamente una cienmilésima el exponente de la mejor marca anterior. La magnitud de la ganancia es típica de los laboriosos avances que se han producido recientemente en este campo.
Para adquirir una idea de este proceso y de cómo podría mejorarse, empecemos con un par de matrices 2 × 2, A y B. Para calcular cada elemento de su matriz producto, usamos la correspondiente fila de A y la correspondiente columna de B. Así, para obtener el elemento superior derecho, multiplicamos el primer número de la primera fila de A por el primer número de la segunda columna de B, luego multiplicamos el segundo número de la primera fila de A por el segundo número de la segunda columna de B, y sumamos esos dos productos.
Esta operación se conoce como el «producto escalar» de una fila y una columna. Para calcular el resto de elementos de la matriz producto, hay que repetir el procedimiento con las respectivas filas y columnas.
En total, el método clásico para multiplicar matrices 2 × 2 requiere 8 multiplicaciones y algunas sumas. Y, en general, para obtener el producto de dos matrices n × n de esta forma hay que hacer n3 multiplicaciones.
A medida que aumenta el tamaño de las matrices, el número de multiplicaciones necesarias para hallar su producto crece mucho más rápido que el número de sumas. Para hallar el producto de dos matrices 2 × 2 se necesitan 8 multiplicaciones intermedias, mientras que con matrices 4 × 4 precisaremos 64. Sin embargo, el número de sumas implicadas en ambos productos es mucho más parejo. En general, hay tantas sumas como elementos en la matriz, es decir, 4 para las matrices 2 × 2 y 16 para las matrices 4 × 4. Esta diferencia entre la suma y la multiplicación ya empieza a dejar claro por qué los investigadores miden la velocidad del producto de matrices exclusivamente en función del número de multiplicaciones requeridas.
«Las multiplicaciones lo son todo», incide Umans. «El exponente del tiempo de ejecución depende solo del número de multiplicaciones. Podríamos decir que las sumas desaparecen.»
Durante siglos, se pensó que n3 constituía el límite de «velocidad» para el producto de matrices. Al parecer, en 1969, Volker Strassen se propuso demostrar que no había forma de multiplicar matrices 2 × 2 usando menos de 8 multiplicaciones. Pero no pudo encontrar la prueba, y al cabo de un tiempo comprendió por qué: ¡en realidad hay una manera de hacerlo con 7!
Strassen concibió un complicado conjunto de relaciones que le permitieron sustituir una de esas 8 multiplicaciones por 14 sumas adicionales. Puede que no parezca una gran diferencia, pero sí lo es, gracias al mayor peso de la multiplicación en comparación con la suma. Y al descubrir la forma de ahorrarse una única multiplicación en matrices 2 × 2, Strassen halló un resquicio que podía explotar al multiplicar matrices más grandes.
«Esa pequeña mejora conduce a enormes ganancias con matrices grandes», afirma Vassilevska Williams.
Pongamos por caso que queremos multiplicar dos matrices 8 × 8. Una forma de hacerlo es dividir cada matriz en cuatro matrices 4 × 4. Dado que los elementos de una matriz también pueden ser matrices, podemos pensar en las matrices originales como un par de matrices 2 × 2, cada uno de cuyos 4 elementos es a su vez una matriz 4 × 4. Tras algunas manipulaciones, cada una de estas matrices 4 × 4 puede dividirse también en cuatro matrices 2 × 2.
Lo que hace útil esta reducción (donde se dividen repetidamente las matrices más grandes en otras más pequeñas) es que podemos aplicar el algoritmo de Strassen una y otra vez a las matrices más pequeñas, cosechando las ganancias de su método en cada paso. En total, el algoritmo de Strassen redujo el número de pasos multiplicativos necesarios para calcular un producto de matrices de n3 a n2,81.
La siguiente gran mejora llegó a finales de los años 70, cuando se desarrolló una forma esencialmente nueva de abordar el problema, que implica traducir el producto de matrices en un problema computacional distinto donde intervienen unos objetos algebraicos llamados tensores. Los tensores concretos que se emplean en este problema son conjuntos tridimensionales de números compuestos por muchas partes diferentes, cada una de las cuales se asemeja a un pequeño problema de multiplicación de matrices.
El producto de matrices y este problema en el que intervienen los tensores son equivalentes en cierto sentido, pero los investigadores ya disponían de procedimientos más rápidos para resolver el segundo. Eso les dejó la tarea de determinar el «tipo de cambio» entre ambos problemas: ¿Qué tamaño tienen las matrices que se pueden multiplicar con el mismo coste computacional que conlleva resolver el problema de los tensores?
«Se trata de un paradigma muy común en la ciencia computacional teórica: reducir unos problemas a otros para mostrar que son igual de fáciles o difíciles», señala Alman.
En 1981, Arnold Schönhage empleó esa estrategia para demostrar que es posible realizar el producto de matrices en n2,522 pasos. Más adelante, Strassen bautizaría este enfoque como el «método láser».
En las últimas décadas, todos los avances en la multiplicación de matrices han llegado gracias a mejoras en el método láser, ya que los investigadores han encontrado formas cada vez más eficientes de pasar de un problema al otro. En su nueva demostración, Alman y Vassilevska Williams reducen la fricción entre ambos problemas y demuestran que es posible «comprar» más producto de matrices del que se pensaba hasta ahora para resolver un problema tensorial de un tamaño dado.
«En esencia, Josh y Virginia han encontrado una manera de ajustar la maquinaria del método láser para obtener resultados aún mejores», explica Henry Cohn, de Microsoft Research.
El artículo mejora la máxima velocidad teórica con la que se pueden multiplicar dos matrices hasta n2,3728596.
También le permite a Vassilevska Williams recuperar el récord del producto de matrices, que ya ostentó en 2012 (n2,372873) y luego perdió en 2014 ante François Le Gall (n2,3728639).
Sin embargo, pese a todos los esfuerzos, también está claro que este método proporciona cada vez menos réditos. De hecho, es posible que la mejora de Alman y Vassilevska Williams se acerque al máximo de lo que se puede lograr con el método láser. Y aún estamos muy lejos de la meta teórica definitiva.
«No es probable que demos el salto al exponente 2 usando esta familia concreta de métodos», opina Umans.
Para conseguirlo, habrá que descubrir nuevas técnicas y mantener la fe en que es realmente posible.
Vassilevska Williams rememora una conversación que tuvo en una ocasión con Strassen sobre este particular. «Le pregunté si pensaba que era posible llegar [al exponente 2] en el producto de matrices y respondió «no, no, no, no, no».»
Kevin Hartnett/Quanta Magazine
Artículo original traducido por Investigación y Ciencia con el permiso de QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión pública de la ciencia.
Referencia: «A refined laser method and faster matrix multiplication», Josh Alman y Virginia Vassilevska Williams en arXiv:2010.05846 [cs.DS], 12 de octubre de 2020.
