Catálogo de publicaciones - tesis
Título de Acceso Abierto
Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
Nardo Giménez Guillermo Matera Pablo Solernó
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
La resolución de sistemas de ecuaciones polinomiales y la interpolación polinomial multivariada se analizan desde el punto de vista algorítmico y de la complejidad computacional. Desde el punto de vista algorítmico se exhibe un algoritmo probabilístico que resuelve un sistema polinomial cuya complejidad bit es esencialmente cuadrática en el número de Bézout del sistema y lineal en su talla bit. Este algoritmo resuelve el sistema de entrada módulo un número primo p y aplica levantamiento p–ádico. Para esto, 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 preserva ciertas propiedades geométricas y algebraicas fundamentales del sistema original. Luego este algoritmo se aplica al problema de la interpolación polinomial cuando el conjunto 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 usan bases de Grobner o H–bases en el peor caso y en ciertos casos de interés práctico puede resultar considerablemente menor. Desde el punto de vista de la complejidad computacional se demuestran cotas inferiores para la complejidad de los problemas de interpolación polinomial. Se introduce un nuevo modelo computacional para la interpolación de Hermite–Lagrange que incluye clases no lineales de interpolantes. Este modelo incluye fenómenos de coalescencia y captura una gran variedad de conocidos problemas y algoritmos de interpolación. En este contexto, se exhiben ejemplos de problemas de interpolación con clases no lineales de interpolantes cuya complejidad es intrínsecamente exponencial, mostrando que nuestro algoritmo para interpolación polinomial multivariada es esencialmente asintóticamente óptimo para los problemas seleccionados y que nada se gana admitiendo no linealidad.Palabras clave – provistas por el repositorio digital
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
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2017 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2017-08-25
Información sobre licencias CC
