Tesis > Documento


Ver el documento (formato PDF)   Waissbein, Ariel.  "Algoritmos de deformación para la resolución de sistemas polinomiales"  (2013)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
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.

Abstract:
This thesis is devoted to computational tasks of basic algebraic geometry in characteristic zero. We aim to analyse and discover the complexity of problems defined by systems of polynomial equations from a computer algebra perspective. The computational intractability of a general approach to geometric elimination problems compels us to study the difficulty of elimination for particular families of polynomial equation systems where worst-case complexity is tractable (and significantly lower than the complexity of tackling the general case). When possible, we provide an efficient solution method. As our “compass” for determining these families, we use deformation techniques which, we will show, are susceptible to problems with well-posed semantic properties. Hence, this work consists in establishing some elimination problems that are tractable, and for these, exhibiting efficient algorithms that tackle them. Our deformation techniques rely on a Newton-Hensel lifting procedure which adapts well in order to obtain algorithms running in fewer steps when certain semantic parameters are “low”. Using highly-efficient algorithms for constructing these geometric elimination procedures, we develop a catalogue of results on polynomial system solving that improve over the prior art.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Algoritmos de deformación para la resolución de sistemas polinomiales     =    Deformation algorithms for polynomial system solving
Autor : Waissbein, Ariel
Director : Matera, Guillermo
Consejero : Matera, Guillermo
Jurados : Dickenstein, Alicia  ; Pardo, Luis Miguel  ; Sabia, Juan
Año : 2013
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Matemática
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias Matemáticas
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5473_Waissbein
Idioma : Inglés
Area Temática : Matemática / Álgebra
Palabras claves : ALGORITMOS EFICIENTES; ECUACIONES POLINOMIALES; ELIMINACION GEOMETRICA; LEVANTAMIENTO DE NEWTON-HENSEL; ALGORITMOS SIMBOLICOS; ALGORITMOS PROBABILISTICOS; COMPLEJIDAD; EFFICIENT ALGORITHMS; POLYNOMIAL EQUATIONS; GEOMETRIC ELIMINATION; NEWTON-HENSEL LIFTING; SYMBOLIC ALGORITHMS; PROBABILISTIC ALGORITHMS; COMPLEXITY
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34