Abstract:

Una estrategia habitual para mejorar un algoritmo es la paralelización: se divide la tarea a realizar en tareas más pequeñas que pueden ejecutarse simultáneamente. Por ejemplo, hay formas de traducir el problema de multiplicar dos matrices a muchas multiplicaciones independientes de matrices de menor tamaño. Una manera de implementar esto con una red de nodos de computación es como sigue: un nodo maestro divide la tarea y envía cada subtarea a un nodo trabajador. Al terminar su ejecución, cada nodo trabajador devuelve su resultado al nodo maestro. Cuando este obtiene todos los resultados, entonces recupera el resultado de la tarea original.

En el método anterior, el algoritmo será tan lento como el nodo trabajador que más tarde en responder, pues el nodo maestro espera a tener todas las respuestas. Si la cantidad de nodos trabajadores es muy grande, entonces también lo será la diferencia esperada entre sus tiempos de ejecución. Para mitigar este efecto, debemos de diseñar un algoritmo que nos permita recuperar el resultado de nuestra tarea original sin necesidad de obtener todas las respuestas de los nodos trabajadores.

En esta charla nos centraremos en la multiplicación de matrices definidas sobre un cuerpo finito. Empezaremos explicando una solución clásica que se sirve de la interpolación de Lagrange (códigos Reed-Solomon) y, luego, pasaremos a mostrar nuestra generalización que utiliza interpolación de funciones algebraicas (códigos algebrogeométricos), permitiendo así utilizar una mayor cantidad de nodos trabajadores. Traduciremos el problema de encontrar algoritmos eficientes a un problema combinatorio planteado exclusivamente en términos del semigrupo de Weierstrass, el cual resolveremos.

Este es un trabajo conjunto con Umberto Martínez-Peñas.