Continuación homotópica para la resolución de sistemas de polinomios

Abstract

Este Trabajo de Fin de Grado está dedicado a la explicación del método de continuación homotópica, haciendo especial énfasis en su aplicación a la resolución de sistemas de ecuaciones polinomiales cuadrados. En primer lugar se definen los sistemas de polinomios y se proporcionan diversas aplicaciones actuales de los mismos. Seguidamente se introducen los fundamentos teóricos de la continuación homotópica, detallando en especial el método de seguimiento de caminos o path-tracking con homotopías de combinación convexa. Se expone un algoritmo general para su desarrollo. A continuación se presenta un programa informático desarrollado por el autor, diseñado para poder modelar cualquier sistema de ecuaciones polinomiales y probar los diversos métodos de seguimiento de caminos. Este desarrollo práctico permite una experimentación controlada así como una evaluación de los métodos usando los datos que se obtienen. Finalmente se discute la eficiencia y el éxito de cuatro algoritmos de seguimiento de caminos específicos, los cuales son probados y comparados mediante el uso de varios sistemas predefinidos.

This Final Project is dedicated to explaining the homotopy continuation method, with a special emphasis on its application to solving square polynomial equation systems. Firstly, polynomial systems are defined, and various current applications of these systems are provided. Next, the theoretical foundations of homotopy continuation are introduced, detailing in particular the path-tracking method with convex combination homotopies. A general algorithm for its development is also presented. Then, a computer program developed by the author is provided. This program is designed to model any polynomial system of equations, and to test various path-tracking methods. This practical development allows for controlled experimentation and an evaluation of the methods using the data obtained. Finally, the efficiency and success of four specific path-tracking algorithms are discussed. These algorithms are tested and compared using a collection of predefined systems.