Algoritmos de deformación para la resolución de sistemas polinomiales

Mostrar todas las versiones(3)

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 en...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Waissbein, Ariel
Formato: Tesis Doctoral
Lenguaje:Inglés
Publicado: 2013
Materias:
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
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n5473_Waissbein
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n5473_Waissbein
record_format dspace
spelling todo:tesis_n5473_Waissbein2023-10-03T12:57:38Z Algoritmos de deformación para la resolución de sistemas polinomiales Deformation algorithms for polynomial system solving Waissbein, Ariel 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 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. 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. Fil: Waissbein, Ariel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2013 Tesis Doctoral PDF Inglés info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n5473_Waissbein
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv Inglés
topic 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
spellingShingle 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
Waissbein, Ariel
Algoritmos de deformación para la resolución de sistemas polinomiales
topic_facet 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
description 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.
format Tesis Doctoral
author Waissbein, Ariel
author_facet Waissbein, Ariel
author_sort Waissbein, Ariel
title Algoritmos de deformación para la resolución de sistemas polinomiales
title_short Algoritmos de deformación para la resolución de sistemas polinomiales
title_full Algoritmos de deformación para la resolución de sistemas polinomiales
title_fullStr Algoritmos de deformación para la resolución de sistemas polinomiales
title_full_unstemmed Algoritmos de deformación para la resolución de sistemas polinomiales
title_sort algoritmos de deformación para la resolución de sistemas polinomiales
publishDate 2013
url https://hdl.handle.net/20.500.12110/tesis_n5473_Waissbein
work_keys_str_mv AT waissbeinariel algoritmosdedeformacionparalaresoluciondesistemaspolinomiales
AT waissbeinariel deformationalgorithmsforpolynomialsystemsolving
_version_ 1782023903314444288

Ejemplares similares