Tesis
Algoritmos de deformación para la resolución de sistemas polinomiales
Deformation algorithms for polynomial system solving
Autor
Waissbein, Ariel
Institución
Resumen
Esta tesis está dedicada a ciertas tareas computacionales de geometría algebraica en característica cero. Apuntamos a analizar y descubrir la complejidad de problemas definidos por sistemas de ecuaciones polinomiales con una perspectiva de álgebra computacional. La intratabilidad computacional de los enfoques generalistas a los problemas de geometría computacional nos impele a estudiar familias particulares de sistemas de ecuaciones polinomiales en los que la complejidad del peor caso es tratable (y significativamente más baja que la del caso general). Cuando sea posible, proveeremos un método eficiente para encontrar su solución. Como “brújula” para determinar estas familias usamos técnicas de deformación las que, según mostraremos, son sensibles a problemas con buenas propiedades semánticas. Entonces, este trabajo consiste en establecer algunos problemas de eliminación que son tratables y exhibir algoritmos eficientes que los resuelven. Nuestras técnicas de deformación se basan en un procedimiento de levantamiento à la Newton–Hensel que se adapta bien para producir algoritmos que corren en menos pasos cuando las propiedades semánticas referenciadas anteriormente son buenas. Construiremos, entonces, un catálogo de resultados sobre la resolución de sistemas de ecuaciones polinomiales, usando algoritmos de álgebra altamente eficientes, que constituyen mejoras en relación con el estado del arte.