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.


Preprints Preprints en arXiv


2022

 Generalized Perron Roots and Solvability of the Absolute Value EquationarXiv:1912.08157

(Junto a Manuel Radons)

 A $p$-adic Descartes solver: the Strassman solverarXiv:2203.07016


 Probabilistic bounds on best rank-one approximation ratioarXiv:2201.02191


Artículos científicos de revista


2023

 Condition Numbers for the Cube.
 I: Univariate Polynomials and HypersurfacesarXiv:2006.04423

J. Tonelli-Cueto and E. Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces (Inglés) [Números de Condición para el Cubo. I: Polinomios Univariados e Hipersuperficies], Journal of Symbolic Computation, 115:142-173, 2023. First on-line: August 2022. DOI 10.1016/j.jsc.2022.08.013
Journal version of Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces in the Special Issue of ISSAC'20.

2022

 Functional norms, condition numbers
 and numerical algorithms in algebraic geometry arXiv:2102.11727 OA paper

F. Cucker, A.A. Ergür and J. Tonelli-Cueto. Functional norms, condition numbers and numerical algorithms in algebraic geometry (Inglés) [Normas funcionales, números de condición y algoritmos numéricos], Forum of Mathematics, Sigma, 10:e103, 2022. DOI 10.1017/fms.2022.89

 A Geometric Summation of the Geometric Serieshal-03779492

J. Tonelli-Cueto. A Geometric Summation of the Geometric Series (Inglés) [Una Suma Geométrica de la Serie Geométrica], The American Mathematical Monthly, 129(10):974, 2022. DOI 10.1080/00029890.2022.2115825 [AM for downloading]

 On the Complexity of the Plantinga-Vegter AlgorithmarXiv:2004.06879

F. Cucker, A.A. Ergür and J. Tonelli-Cueto. On the Complexity of the Plantinga-Vegter Algorithm (Inglés) [Sobre la Complejidad del Algoritmo Plantinga-Vegter], Discrete & Computational Geometry, 68(3):664–708, 2022. DOI 10.1007/s00454-022-00403-x [SharedIt LINK]
Versión de revista de Plantinga-Vegter algorithm takes average polynomial time.

2021

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

P. Bürgisser, F. Cucker y J. Tonelli-Cueto. Computing the Homology of Semialgebraic Sets. II: General Formulas (Inglés) [Computando la Homología de los Conjuntos Semialgebraicos. II: Fórmulas Generales], Foundations of Computational Mathematics, 21(5):1279–1316, 2021. First on-line: January 2021. DOI 10.1007/s10208-020-09483-8 [SharedIt LINK]

2020

 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 los Conjuntos Semialgebraicos. I: Fórmulas Laxas], Foundations of Computational Mathematics, 20(1):71-119, 2020. First on-line: May 2019. DOI 10.1007/s10208-019-09418-y [SharedIt LINK]

2019

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

P. Bürgisser, A.A. Ergür y J. Tonelli-Cueto. On the Number of Real Zeros of Random Fewnomials (Inglés) [Sobre el Número de Ceros Reales de los Oligonomios Aleatorios], SIAM Journal on Applied Algebra and Geometry, 3(4):721–732, 2019. DOI 10.1137/18M1228682

Artículos científicos de conferencia


2022

 Beyond Worst-Case Analysis for Root Isolation AlgorithmsarXiv:2202.06428v3

A.A. Ergür, J. Tonelli-Cueto y E. Tsigaridas. Beyond Worst-Case Analysis for Root Isolation Algorithms (Inglés) [Más allá del Análisis del Peor Caso en Algoritmos de Aislamiento de Raíces]. En Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC'22, páginas 139–148. ACM, 2022. DOI 10.1145/3476446.3535475 [Author-Ized LINK]

 On the Error of Random Sampling:
Uniformly Distributed Random Points on Parametric CurvesarXiv:2203.02832v2

A. Chalkis, Ch. Katsamaki y J. Tonelli-Cueto. On the Error of Random Sampling: Uniformly Distributed Random Points on Parametric Curves (Inglés) [Sobre el Error del Sampleo Aleatorio: Puntos Uniformemente Distribuidos en Curvas Paramétricas]. En Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC'22, páginas 273–282. ACM, 2022. DOI 10.1145/3476446.3536190 [Author-Ized LINK]

 Ultrametric Smale's $\alpha$-theoryarXiv:2206.08392

J.G. Suchen and J. Tonelli-Cueto. Ultrametric Smale's $\alpha$-theory (Inglés) [Teoría $\alpha$ de Smale Ultramétrica], ACM Communications in Computer Algebra, 56(2):56-59, June 2022. DOI 10.1145/3572867.3572875 [Author-Ized LINK]

 Generalized Perron roots and solvability of the absolute value equationhal-03739462

M. Radons y J. Tonelli-Cueto. Generalized Perron roots and solvability of the absolute value equation (Inglés) [Raíces generalizadas de Perron y la ecuación del valor absoluto]. En L.F. Tabera Alonso (ed.), Discrete Mathematics Days 2022, páginas 237-242. Editorial Universidad de Cantabria, 2022. DOI 10.22429/Euc2022.016

2020

 Condition Numbers for the Cube.
 I: Univariate Polynomials and HypersurfacesarXiv:2006.04423v1

J. Tonelli-Cueto y E. Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces (Inglés) [Números de Condición para el Cubo. I: Polinomios Univariados e Hipersuperficies]. En Proceedings of the 2020 International Symposium on Symbolic and Algebraic Computation, ISSAC'20, páginas 434-441. ACM, 2020. DOI 10.1145/3373207.3404054 [Author-Ized LINK]

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 Promedio Polinónimo]. En Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation, ISSAC'19, páginas 114-121. ACM, 2019. DOI 10.1145/3326229.3326252 [Author-Ized LINK]

Otras publicaciones


Tesis


2019

 Condition and Homology in Semialgebraic Geometrytesis doctoral

J. Tonelli-Cueto. Condition and Homology in Semialgebraic Geometry (Inglés) [Condición y Homología en Geometría Semialgebraica]. Tesis doctoral, Technsiche Universität Berlin, Repositorio DepositOnce, diciembre 2019. DOI 10.14279/depositonce-9453