Optimization of Wu's algorithm for the elimination of polynomial variables by High-Performance Computing (HPC)

Abstract

El método de conjunto característico nace de la unión de la geometría a y teoría de la eliminación. J. Ritt inició su estudio en el campo de prime ideals, y más tarde W. Wu ampliaría su uso al campo de razonamiento geométrico, caracterización de variedades y aplicaciones en diversos campos, por ejemplo, prueba automática de teoremas, visión por computador, química, robótica, entre otros. Sin embargo, debido a su complejidad teórica el método requiere de un elevado costo computacional, este costo es teóricamente menor a otras métodos existentes, como método de Gröbner o métodos de Resultants. Sin embargo, la complejidad de los métodos de eliminación no pueden generalizarse para todas las ecuaciones algebraicas. A diferencia de otros métodos, el método de conjunto característico no cuenta con un estudio realizado sobre su implementación con una perspectiva de programación paralela. Por lo cual este proyecto de graduación se centra en la construcción de un algoritmo basado en el modelo propuesto por Ritt and Wu que computa elementos de la cadena ascendente en paralelo, optimizando el modelo con el uso de computaciones fusionadas. Usamos programación funcional para manejar la memoria y los hilos del sistema operativo; el modelo implementado usa paralelización anidada del cual encontramos el menor tiempo de cálculo del algoritmo.