Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada

Mostrar todas las versiones(3)

La resolución de sistemas de ecuaciones polinomiales y la interpolación polinomialmultivariada se analizan desde el punto de vista algorítmico y de la complejidadcomputacional. Desde el punto de vista algorítmico se exhibe un algoritmo probabilístico queresuelve un sistema polinomial cuya complejida...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Giménez, Nardo
Otros Autores: Matera, Guillermo
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2017
Materias:
RESOLUCION DE SISTEMAS POLINOMIALES SOBRE Q
COMPLEJIDAD BIT
SUCESION REGULAR REDUCIDA
FORMA DE CHOW
FIBRAS DE LEVANTAMIENTO
LEVANTAMIENTO DE HENSEL
PRIMOS LUCKY
INTERPOLACION DE HERMITE-LAGRANGE
PROBLEMA DE INTERPOLACION
ALGORITMO DE INTERPOLACION
COMPLEJIDAD COMPUTACIONAL
COTA INFERIOR DE COMPLEJIDAD
APLICACION CONSTRUIBLE
APLICACION RACIONAL
APLICACION TOPOLOGICAMENTE ROBUSTA
APLICACION GEOMETRICAMENTE ROBUSTA
POLYNOMIAL SYSTEM SOLVING OVER Q
BIT COMPLEXITY
REDUCED REGULAR SEQUENCE
CHOW FORM
LIFTING FIBERS
HENSEL LIFTING
LUCKY PRIMES
HERMITE-LAGRANGE INTERPOLATION
INTERPOLATION PROBLEM
INTERPOLATION ALGORITHM
COMPUTATIONAL COMPLEXITY
LOWER COMPLEXITY BOUND
CONSTRUCTIBLE MAP
RATIONAL MAP
TOPOLOGICALLY ROBUST MAP
GEOMETRICALLY ROBUST MAP
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n6302_Gimenez
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6302_Gimenez_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n6302_Gimenez_oai
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
topic RESOLUCION DE SISTEMAS POLINOMIALES SOBRE Q
COMPLEJIDAD BIT
SUCESION REGULAR REDUCIDA
FORMA DE CHOW
FIBRAS DE LEVANTAMIENTO
LEVANTAMIENTO DE HENSEL
PRIMOS LUCKY
INTERPOLACION DE HERMITE-LAGRANGE
PROBLEMA DE INTERPOLACION
ALGORITMO DE INTERPOLACION
COMPLEJIDAD COMPUTACIONAL
COTA INFERIOR DE COMPLEJIDAD
APLICACION CONSTRUIBLE
APLICACION RACIONAL
APLICACION TOPOLOGICAMENTE ROBUSTA
APLICACION GEOMETRICAMENTE ROBUSTA
POLYNOMIAL SYSTEM SOLVING OVER Q
BIT COMPLEXITY
REDUCED REGULAR SEQUENCE
CHOW FORM
LIFTING FIBERS
HENSEL LIFTING
LUCKY PRIMES
HERMITE-LAGRANGE INTERPOLATION
INTERPOLATION PROBLEM
INTERPOLATION ALGORITHM
COMPUTATIONAL COMPLEXITY
LOWER COMPLEXITY BOUND
CONSTRUCTIBLE MAP
RATIONAL MAP
TOPOLOGICALLY ROBUST MAP
GEOMETRICALLY ROBUST MAP
spellingShingle RESOLUCION DE SISTEMAS POLINOMIALES SOBRE Q
COMPLEJIDAD BIT
SUCESION REGULAR REDUCIDA
FORMA DE CHOW
FIBRAS DE LEVANTAMIENTO
LEVANTAMIENTO DE HENSEL
PRIMOS LUCKY
INTERPOLACION DE HERMITE-LAGRANGE
PROBLEMA DE INTERPOLACION
ALGORITMO DE INTERPOLACION
COMPLEJIDAD COMPUTACIONAL
COTA INFERIOR DE COMPLEJIDAD
APLICACION CONSTRUIBLE
APLICACION RACIONAL
APLICACION TOPOLOGICAMENTE ROBUSTA
APLICACION GEOMETRICAMENTE ROBUSTA
POLYNOMIAL SYSTEM SOLVING OVER Q
BIT COMPLEXITY
REDUCED REGULAR SEQUENCE
CHOW FORM
LIFTING FIBERS
HENSEL LIFTING
LUCKY PRIMES
HERMITE-LAGRANGE INTERPOLATION
INTERPOLATION PROBLEM
INTERPOLATION ALGORITHM
COMPUTATIONAL COMPLEXITY
LOWER COMPLEXITY BOUND
CONSTRUCTIBLE MAP
RATIONAL MAP
TOPOLOGICALLY ROBUST MAP
GEOMETRICALLY ROBUST MAP
Giménez, Nardo
Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
topic_facet RESOLUCION DE SISTEMAS POLINOMIALES SOBRE Q
COMPLEJIDAD BIT
SUCESION REGULAR REDUCIDA
FORMA DE CHOW
FIBRAS DE LEVANTAMIENTO
LEVANTAMIENTO DE HENSEL
PRIMOS LUCKY
INTERPOLACION DE HERMITE-LAGRANGE
PROBLEMA DE INTERPOLACION
ALGORITMO DE INTERPOLACION
COMPLEJIDAD COMPUTACIONAL
COTA INFERIOR DE COMPLEJIDAD
APLICACION CONSTRUIBLE
APLICACION RACIONAL
APLICACION TOPOLOGICAMENTE ROBUSTA
APLICACION GEOMETRICAMENTE ROBUSTA
POLYNOMIAL SYSTEM SOLVING OVER Q
BIT COMPLEXITY
REDUCED REGULAR SEQUENCE
CHOW FORM
LIFTING FIBERS
HENSEL LIFTING
LUCKY PRIMES
HERMITE-LAGRANGE INTERPOLATION
INTERPOLATION PROBLEM
INTERPOLATION ALGORITHM
COMPUTATIONAL COMPLEXITY
LOWER COMPLEXITY BOUND
CONSTRUCTIBLE MAP
RATIONAL MAP
TOPOLOGICALLY ROBUST MAP
GEOMETRICALLY ROBUST MAP
description La resolución de sistemas de ecuaciones polinomiales y la interpolación polinomialmultivariada se analizan desde el punto de vista algorítmico y de la complejidadcomputacional. Desde el punto de vista algorítmico se exhibe un algoritmo probabilístico queresuelve un sistema polinomial cuya complejidad bit es esencialmente cuadrática enel número de Bézout del sistema y lineal en su talla bit. Este algoritmo resuelve elsistema de entrada módulo un número primo p y aplica levantamiento p–ádico. Paraesto, se establecen una serie de resultados sobre la longitud bit de un primo “lucky” p,es decir un primo para el cual la reducción del sistema de entrada módulo p preservaciertas propiedades geométricas y algebraicas fundamentales del sistema original. Luego este algoritmo se aplica al problema de la interpolación polinomial cuando elconjunto de nodos está dado como el conjunto de ceros de un sistema polinomial,dando como resultado un procedimiento que calcula intepolantes de “bajo grado”. La complejidad bit de estos algoritmos es similar a la de los algoritmos que usanbases de Grobner o H–bases en el peor caso y en ciertos casos de interés prácticopuede resultar considerablemente menor. Desde el punto de vista de la complejidad computacional se demuestran cotasinferiores para la complejidad de los problemas de interpolación polinomial. Se introduceun nuevo modelo computacional para la interpolación de Hermite–Lagrangeque incluye clases no lineales de interpolantes. Este modelo incluye fenómenos decoalescencia y captura una gran variedad de conocidos problemas y algoritmos deinterpolación. En este contexto, se exhiben ejemplos de problemas de interpolacióncon clases no lineales de interpolantes cuya complejidad es intrínsecamente exponencial,mostrando que nuestro algoritmo para interpolación polinomial multivariada esesencialmente asintóticamente óptimo para los problemas seleccionados y que nadase gana admitiendo no linealidad.
author2 Matera, Guillermo
author_facet Matera, Guillermo
Giménez, Nardo
format Tesis doctoral
Tesis doctoral
publishedVersion
author Giménez, Nardo
author_sort Giménez, Nardo
title Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
title_short Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
title_full Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
title_fullStr Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
title_full_unstemmed Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
title_sort sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2017
url https://hdl.handle.net/20.500.12110/tesis_n6302_Gimenez
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6302_Gimenez_oai
work_keys_str_mv AT gimeneznardo sobrelacomplejidaddelaresoluciondesistemasdeecuacionespolinomialesydelainterpolacionpolinomialmultivariada
AT gimeneznardo onthecomplexityofpolynomialsystemsolvingandmultivariatepolynomialinterpolation
_version_ 1766015944524562432
spelling I28-R145-tesis_n6302_Gimenez_oai2023-04-26 Matera, Guillermo Solernó, Pablo Giménez, Nardo 2017-08-25 La resolución de sistemas de ecuaciones polinomiales y la interpolación polinomialmultivariada se analizan desde el punto de vista algorítmico y de la complejidadcomputacional. Desde el punto de vista algorítmico se exhibe un algoritmo probabilístico queresuelve un sistema polinomial cuya complejidad bit es esencialmente cuadrática enel número de Bézout del sistema y lineal en su talla bit. Este algoritmo resuelve elsistema de entrada módulo un número primo p y aplica levantamiento p–ádico. Paraesto, se establecen una serie de resultados sobre la longitud bit de un primo “lucky” p,es decir un primo para el cual la reducción del sistema de entrada módulo p preservaciertas propiedades geométricas y algebraicas fundamentales del sistema original. Luego este algoritmo se aplica al problema de la interpolación polinomial cuando elconjunto de nodos está dado como el conjunto de ceros de un sistema polinomial,dando como resultado un procedimiento que calcula intepolantes de “bajo grado”. La complejidad bit de estos algoritmos es similar a la de los algoritmos que usanbases de Grobner o H–bases en el peor caso y en ciertos casos de interés prácticopuede resultar considerablemente menor. Desde el punto de vista de la complejidad computacional se demuestran cotasinferiores para la complejidad de los problemas de interpolación polinomial. Se introduceun nuevo modelo computacional para la interpolación de Hermite–Lagrangeque incluye clases no lineales de interpolantes. Este modelo incluye fenómenos decoalescencia y captura una gran variedad de conocidos problemas y algoritmos deinterpolación. En este contexto, se exhiben ejemplos de problemas de interpolacióncon clases no lineales de interpolantes cuya complejidad es intrínsecamente exponencial,mostrando que nuestro algoritmo para interpolación polinomial multivariada esesencialmente asintóticamente óptimo para los problemas seleccionados y que nadase gana admitiendo no linealidad. Polynomial system solving and multivariate polynomial interpolation over therationals are considered from both the algorithmic and computational point of view. From the algorithmic point of view a probabilistic algorithm is developed whichsolves a polynomial system whose bit complexity is roughly quadratic in the B´ezoutnumber of the system and linear in its bit size. Our algorithm solves the input systemmodulo a prime number p and applies p–adic lifting. For this purpose, we establisha number of results on the bit length of a “lucky” prime p, namely one for whichthe reduction of the input system modulo p preserves certain fundamental geometricand algebraic properties of the original system. Then this algorithm is applied topolynomial interpolation when the set of nodes is given as the set of zeros of apolynomial system, yielding a procedure which computes “low degree” interpolants. The bit complexity of these algorithms is similar to that of the algorithms that use Grobner or H–bases in the worst case, and in certain cases of particular interest canbe significantly lower. From the computational complexity point of view lower complexity bounds forthe complexity of interpolation algorithms by polynomials are shown. A new computationalmodel for Hermite–Lagrange interpolation with nonlinear classes of interpolantsis introduced, which includes coalescence phenomena and captures a largevariety of known Hermite–Lagrange interpolation problems and algorithms. In thiscontext examples of interpolation problems are exhibited with nonlinear classes ofinterpolants whose complexity is intrinsically exponential, showing that our algorithmfor multivariate polynomial interpolation is essentially asymptotically optimalfor the problems under consideration and that nothing is gained by admittingnonlinearity. Fil: Giménez, Nardo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n6302_Gimenez spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar RESOLUCION DE SISTEMAS POLINOMIALES SOBRE Q COMPLEJIDAD BIT SUCESION REGULAR REDUCIDA FORMA DE CHOW FIBRAS DE LEVANTAMIENTO LEVANTAMIENTO DE HENSEL PRIMOS LUCKY INTERPOLACION DE HERMITE-LAGRANGE PROBLEMA DE INTERPOLACION ALGORITMO DE INTERPOLACION COMPLEJIDAD COMPUTACIONAL COTA INFERIOR DE COMPLEJIDAD APLICACION CONSTRUIBLE APLICACION RACIONAL APLICACION TOPOLOGICAMENTE ROBUSTA APLICACION GEOMETRICAMENTE ROBUSTA POLYNOMIAL SYSTEM SOLVING OVER Q BIT COMPLEXITY REDUCED REGULAR SEQUENCE CHOW FORM LIFTING FIBERS HENSEL LIFTING LUCKY PRIMES HERMITE-LAGRANGE INTERPOLATION INTERPOLATION PROBLEM INTERPOLATION ALGORITHM COMPUTATIONAL COMPLEXITY LOWER COMPLEXITY BOUND CONSTRUCTIBLE MAP RATIONAL MAP TOPOLOGICALLY ROBUST MAP GEOMETRICALLY ROBUST MAP Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada On the complexity of polynomial system solving and multivariate polynomial interpolation info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6302_Gimenez_oai

Ejemplares similares