Investigación

de

Josué Tonelli Cueto


Áreas de interés

Aunque tengo intereses en otras áreas de las matemáticas, mis principales áreas de interes son los algoritmos numéricos y la complejidad basada en condición, la geometría algebraica aleatoria y la geoemtría aleatoria.

Algoritmos numéricos y complejidad basada en condición

Los algoritmos numéricos son algoritmos y por lo tanto discretos en su naturaleza. Estos son especificados por un programa finito y realizan una computación compuesta por una sucesión discreta de operaciones lógicas/aritméticas. Su diferencia con respecto a los algoritmos clásicos yace en que estos tratan con problemas continuos donde el dato de entrada (y salida) están descritos parcialmente por sucesiones de números reales (y complejos). Con estos últimos, el algoritmo numérico puede trabajar solamente con aproximaciones de ellos y no los números reales en sí mismos. En otras palabras, un algoritmo numérico está condenado a funcionar con datos de entrada inexactos, debe redondear los números a medida que se ejecuta y puede producir únicamente respuestas aproximadas para el problema continuo con el que trata (cuando esta respuesta incluye números reales). A pesar de todo esto, los algoritmos numéricos consiguen resolver problemas tanto en teoría como en la práctica. Esto convierte a los algoritmos numéricos en el oximorón por el que lo discreto explora lo continuo.

Analizar la complejidad de los algoritmos numéricos es un desafío. Con ellos, no hay esperanza de que la familiar complejidad del peor caso funcione. No importa cuán pequeño es el error que se permite en las aproximaciones, siempre habrá datos de entrada para los estos errores harán que el algoritmo o bien produzca una respuesta incorrecta o bien nunca pare. Hay dos formas de solucionar este problema: la complejidad del peor caso en datos de entrada restringidos y la complejidad basada en condición.

En la complejidad del peor caso en datos de entrada restringidos, se restringen los datos de entrada que se permiten para el algoritmo numérico. Esta restricción se hace permitiendo únicamente números racionales de tamaño bit acotado en los datos de entrada y considerando únicamente datos de entrada bien puestos, que son aquellos para los que errores “razonablemente” pequeños no afectan “dramáticamente” a la respuesta del problema considerado. Aunque muchas veces exitoso, este analisis de complejidad tiende a dar cotas que están muy lejos del comportamiento observado en la práctica y fracasa a la hora de explicar el fenómeno por el que no todos los datos de entrada toman el mismo tiempo.

En la complejidad basada en condición, se realiza un análisis de complejidad parametrizada en términos de una propiedad del dato de entrada llamada número de condición. El número de condición es una medida cuantitativa de la senibilidad numérica del dato de entrada para el problema continuo dado y dice cuánto varía el dato de salida con respecto a cuánto varía el dato de entrada. Los números de condición pueden variar dependiendo en cómo medimos las variaciones (por ejemplo, norma máxima contra euclídea) y en la naturaleza de las variaciones que consideramos (por ejemplo, peor caso contra promedio). Sin embargo, los números de condición son independiente del algoritmo analizado, son una propiedad geométrica de los datos de entrada con respecto al problema continuo considerado con la que se puede explicar el comportamiento de los algoritmos numéricos en la práctica y porqué algunos datos de entrada requieren más tiempo que otros.

Aun más, la complejidad basada en condición nos permite entender cuánta precisión requiere un algoritmo numérico para garantizar un dato de salida conrrecto y cómo este algoritmo se comporta probabilísticamente, si asumimos una distribución de probabilidad razonable en el dato de entrada. En el primer caseo, la precisión necesitada está generalmente controlada por el logaritmo del número de condición. En el segundo caso, el estudio de la distribución del número de condición de un problema en un dato de entrada aleatorio permite obtener estimaciones de complejidad con alta probabilidad (complejidad débil) y en promedio (complejidad promedio).

Mis intereses se centran en el desarrollo y análisis del algoritmos numéricos para una variedad de problemas (mayoritariamente el geometría algebraica numérica) dentro del marco de la complejidad basada en condición. En esta meta, me interesa en particular desarrollar y analizar algoritmos numéricos basados en subdivisión adaptativa y mejorar los análisis de complejidad existentes explorando, por ejemplo, medidas alternativas de los errores y distribuciones más generales.

Geometría algebraica computacional

La geometría algebraica trata en general con objetos que se pueden definir en función de polinomios y las propiedades de estos objetos. Con la llegada de los ordenadores, la posibilidad de convertir ciertos métodos constructivos, pero humanamente impracticables, en algoritmos útiles se hizo real. Esta posibilidad estaba motivada también por el hecho de que los polinomios aparecen en muchas aplicaciones (brazos robóticos, redes químicas, sistemas dinámicos, etc.), lo que hizo que esta posibilidad se convirtiera además en una necesidad. Esta posibilidad algorítmica es el objeto de estudio de la geometría algebraica computaciones cuya meta es desarrollar y analizar algoritmos que resuelvan problemas en geometría algebraica.

Entre los posibles desafíos computaciones, mi trabajo se centra en la búsqueda de ceros de ecuaciones polinómicas y en la computación de invariantes topológicos de conjuntos semiagebraicos, que son aquellos conjuntos descritos por polinomios reales, desigualdades y sus combinaciones. En el primer problema, me interesa comprender teóricamente mejor los trucos del practicante desde la perspectiva de la complejidad en el caso complejo y los métodos de subdivisión y rejilla en el caso real. En el segundo tema, intento desarrollar un algoritmo que compute la homología de conjuntos semialgebraicos en tiempo medio simplemente exponencial en contraposición al estado del arte actual en el que o bien los algoritmos son doblemente exponenciales en el peor caso o bien simplemente exponenciales con alta probabilidad. Mi proyecto a largo plazo es usar la geometría algebraica computacional para atacar exitósamente la primera parte del décimosexto problema de Hilbert en grados altos.

Geometría aleatoria

Dada una estructura geométrica aleatoria, ¿qué podemos decir acerca de la distribución de sus propiedades? Podemos preguntarnos acerca de las propiedades topológicas del objeto. Por ejemplo, dado un sistema polinomial aleatorio, ¿cuál es la distribución de su numéro de ceros? O, dado un sistema polinomial subdeterminado aleatorio, ¿cuál es la distribución de los números de Betti de su conjunto de ceros? Y podemos considerar también las propiedades geométricas del objeto. Por ejemplo, dado un sistema polinomial aleatorio, ¿cuál es la distribución de la distancia mínima entre dos de sus ceros? O, dado un sistema polinomial subdeterminado aleatorio, ¿cuál es la distribución del alcance (reach) de su conjunto de ceros?

La centralidad de esta pregunta se puede apreciar en varios lugares. Primero, en aplicaciones, esta puede ayudar a comprender por qué ciertos fenómenos son más comunes que otros. Segundo, en los algoritmos constructivos, esta puede ayudar a explicar por qué ciertos métodos fallan a la hora de producir ejemplos de un determinado tipo o por qué producirá exitósamente ejemplos del tipo deseado. Tercero, en geometría lagebraica real, la geometría aleatoria es el único medio de entender qué sucede “en general” dado que, en contraposición al caso complejo, no hay comportamiento genérico en el mundo real.

Mis intereses en geometría aleatoria se centran en la distribución de invariantes topológicos y, por suepuesto, los números de condición de sistemas polinómicos aleatorios. Un meta futura particular es generalizar los métodos actuales en geometría algebraica real aleatoria de distribuciones gaussianas a distribuciones más generales, haciendo las estimaciones probabilísticas actuales más robustas.


Artículos científicos y preprints

Los siguientes son mi artículos científicos y preprints en los últimos años. Para una lista completa, consultar la lista de mi CV o mi lista de preprints de arXiv.




2019

 Computing the Homology of Semialgebraic Sets. II: General FormulasarXiv:1903.10710

(Together with Peter Bürgisser and Felipe Cucker)

2018

 On the Number of Real Zeros of Random Fewnomials arXiv:1811.09425

A aparecer en el SIAM Journal on Applied Algebra and Geometry (SIAGA)

Artículos científicos


2019

 Plantinga-Vegter algorithm takes average polynomial timearXiv:1901.09234

F. Cucker, A.A. Ergür y J. Tonelli-Cueto. Plantinga-Vegter Algorithm takes Average Polynomial Time (Inglés) [El algoritmo de Plantinga-Vegter toma tiempo medio polinómico]. In Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, ISSAC'19, pages 114-121. ACM, New York, 2019. DOI 10.1145/3326229.3326252

 Computing the Homology of Semialgebraic Sets I: Lax FormulasarXiv:1807.06435

P. Bürgisser, F. Cucker y J. Tonelli-Cueto. Computing the Homology of Semialgebraic Sets. I: Lax Formulas (Inglés) [Computando la Homología de Conjuntos Semialgebraicos. I: Fórmulas Laxas], Foundations of Computational Mathematics, May 2019. DOI 10.1007/s10208-019-09418-y


  ©Josué Tonelli-Cueto Código de la página creado por el arte de copiar, pegar y cruzar los dedos