Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | matematica |
| Título: | Algoritmos de deformación para la resolución de sistemas polinomiales |
| Título alternativo: | Deformation algorithms for polynomial system solving |
| Autor: | Waissbein, Ariel |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Departamento de Matemática
|
| Publicación en la Web: | 2014-07-04 |
| Fecha de defensa: | 2013 |
| Fecha en portada: | 2013 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias Matemáticas |
| Director: | Matera, Guillermo |
| Jurado: | Dickenstein, Alicia Marcela; Pardo, Luis Miguel; Sabia, Juan |
| Idioma: | Inglés |
| Palabras clave: | ALGORITMOS EFICIENTES; ECUACIONES POLINOMIALES; ELIMINACION GEOMETRICA; LEVANTAMIENTO DE NEWTON-HENSEL; ALGORITMOS SIMBOLICOS; ALGORITMOS PROBABILISTICOS; COMPLEJIDADEFFICIENT ALGORITHMS; POLYNOMIAL EQUATIONS; GEOMETRIC ELIMINATION; NEWTON-HENSEL LIFTING; SYMBOLIC ALGORITHMS; PROBABILISTIC ALGORITHMS; COMPLEXITY |
| Tema: | matemática/álgebra
|
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n5473_Waissbein |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5473_Waissbein.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n5473_Waissbein |
| Ubicación: | Dep.MAT 005473 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Waissbein, Ariel. (2013). Algoritmos de deformación para la resolución de sistemas polinomiales. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n5473_Waissbein |
Resumen:
Esta tesis está dedicada a ciertas tareas computacionales de geometríaalgebraica en característica cero. Apuntamos a analizar y descubrir la complejidadde problemas definidos por sistemas de ecuaciones polinomiales conuna perspectiva de álgebra computacional. La intratabilidad computacionalde los enfoques generalistas a los problemas de geometría computacional nosimpele a estudiar familias particulares de sistemas de ecuaciones polinomialesen los que la complejidad del peor caso es tratable (y significativamente másbaja que la del caso general). Cuando sea posible, proveeremos un métodoeficiente para encontrar su solución. Como “brújula” para determinar estas familias usamos técnicas de deformaciónlas que, según mostraremos, son sensibles a problemas con buenaspropiedades semánticas. Entonces, este trabajo consiste en establecer algunosproblemas de eliminación que son tratables y exhibir algoritmos eficientesque los resuelven. Nuestras técnicas de deformación se basan en un procedimiento de levantamientoà la Newton–Hensel que se adapta bien para producir algoritmosque corren en menos pasos cuando las propiedades semánticas referenciadasanteriormente son buenas. Construiremos, entonces, un catálogo de resultadossobre la resolución de sistemas de ecuaciones polinomiales, usando algoritmosde álgebra altamente eficientes, que constituyen mejoras en relacióncon el estado del arte.
Abstract:
This thesis is devoted to computational tasks of basic algebraic geometryin characteristic zero. We aim to analyse and discover the complexity of problemsdefined by systems of polynomial equations from a computer algebraperspective. The computational intractability of a general approach to geometricelimination problems compels us to study the difficulty of eliminationfor particular families of polynomial equation systems where worst-case complexityis tractable (and significantly lower than the complexity of tacklingthe general case). When possible, we provide an efficient solution method. As our “compass” for determining these families, we use deformation techniqueswhich, we will show, are susceptible to problems with well-posed semanticproperties. Hence, this work consists in establishing some eliminationproblems that are tractable, and for these, exhibiting efficient algorithms thattackle them. Our deformation techniques rely on a Newton-Hensel lifting procedurewhich adapts well in order to obtain algorithms running in fewer steps whencertain semantic parameters are “low”. Using highly-efficient algorithms forconstructing these geometric elimination procedures, we develop a catalogueof results on polynomial system solving that improve over the prior art.
Citación:
---------- APA ----------
Waissbein, Ariel. (2013). Algoritmos de deformación para la resolución de sistemas polinomiales. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n5473_Waissbein
---------- CHICAGO ----------
Waissbein, Ariel. "Algoritmos de deformación para la resolución de sistemas polinomiales". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2013.https://hdl.handle.net/20.500.12110/tesis_n5473_Waissbein
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5473_Waissbein.pdf
