🔢 mathematics

An adaptive parallel algorithm for computing zeros of analytic functions

Este artículo presenta un algoritmo de C++ paralelo y robusto que combina el conteo adaptativo de ceros, la bisección bidimensional y los métodos de Newton-Kantorovich para computar y certificar eficientemente millones de ceros de funciones analíticas, incluyendo polinomios exponenciales y sumas parciales de la función zeta de Riemann, con alta precisión.

Autores originales: Oswaldo Velásquez Castañón, Manuel Toribio Cangana, Victor Galván Oyola

Publicado 2026-10-01

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Oswaldo Velásquez Castañón, Manuel Toribio Cangana, Victor Galván Oyola

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el vasto paisaje de las matemáticas, existen problemas que parecen simples en la superficie pero que esconden una complejidad inmensa debajo. Uno de estos desafíos consiste en encontrar las "raíces" o ceros de ciertas funciones matemáticas; específicamente, los puntos donde el valor de una función cae a la nada. Si bien hallar un cero para una ecuación simple como "x más dos es igual a cero" es una cuestión de aritmética básica, las funciones estudiadas por los matemáticos en este campo son mucho más intrincadas. Están construidas a partir de combinaciones de crecimiento y decaimiento exponencial, apareciendo a menudo en el estudio de sistemas que cambian con el tiempo con un retraso, como la propagación de una enfermedad o la vibración de una estructura mecánica. Estas funciones se denominan polinomios exponenciales. Otra familia relacionada, conocida como polinomios de Dirichlet, desempeña un papel crucial en la teoría de números, particularmente en la comprensión de la distribución de los números primos. La dificultad radica en que estas funciones pueden tener miles, o incluso millones, de ceros dispersos por el plano complejo, y encontrarlos todos con absoluta certeza es una tarea que a menudo desborda los métodos computacionales estándar.

Un equipo de investigadores ha desarrollado una nueva y robusta forma de abordar este problema. Su trabajo se centra en la creación de un algoritmo que pueda encontrar cada uno de los ceros de estas funciones complejas dentro de un área rectangular específica, garantizando que ninguno se pierda y que la ubicación de cada cero se conozca con extrema precisión. El método está diseñado para ser "adaptativo", lo que significa que puede cambiar su estrategia sobre la marcha dependiendo de lo que encuentre. Si la función se comporta de manera fluida, el algoritmo da pasos grandes para cubrir terreno rápidamente. Si la función gira y se retuerce salvajemente, lo que indica que un cero está cerca, el algoritmo automáticamente reduce la velocidad y hace un acercamiento, dividiendo el área en piezas cada vez más pequeñas hasta que el cero queda aislado. Este proceso es guiado por un principio matemático que cuenta cuántas veces el valor de la función rota alrededor de cero mientras se traza un camino alrededor de una región. Al rastrear cuidadosamente esta rotación, la computadora puede determinar exactamente cuántos ceros se esconden dentro de una caja sin necesidad de verlos directamente.

Para que este proceso sea lo suficientemente rápido como para ser útil, los investigadores construyeron su algoritmo para que se ejecute en múltiples procesadores de computadora simultáneamente. Imagine una sala grande llena de cajas y un equipo de trabajadores encargados de encontrar objetos ocultos dentro de ellas. En lugar de que una sola persona revise cada caja una por una, el equipo divide la sala en secciones, y cada trabajador aborda una sección al mismo tiempo. Los investigadores utilizaron un sistema de pilas protegidas para gestionar este trabajo en equipo, asegurando que ningún par de trabajadores intentara agarrar la misma caja al mismo tiempo, lo que causaría confusión y errores. Una vez que un trabajador aísla una caja que contiene exactamente un cero, cambia a una técnica de refinamiento de alta velocidad para localizar con precisión el lugar exacto del cero. Esta combinación de una búsqueda lenta y cuidadosa para encontrar el vecindario correcto, seguida de una búsqueda rápida y precisa para encontrar el lugar exacto, permite que el sistema maneje cantidades masivas de datos de manera eficiente.

El equipo probó su método en dos tipos principales de funciones. Primero, lo aplicaron a polinomios exponenciales que exhiben tres tipos diferentes de comportamiento, conocidos como retardado, avanzado y neutro, que describen cómo los retrasos afectan el futuro del sistema. Lograron mapear con éxito los ceros de estas funciones, confirmando que el método funciona independientemente del tipo específico de retraso involucrado. Segundo, y quizás de manera más significativa, dirigieron su atención a las sumas parciales de la función zeta de Riemann, un objeto matemático famoso y central para el estudio de los números primos. Computaron los ceros de estas sumas para varios tamaños, que van desde pequeños hasta moderadamente grandes. Al hacerlo, calcularon y certificaron más de 2.5 millones de ceros. Cada uno de estos ceros fue localizado con una tolerancia garantizada de 9.9 por la potencia de 10 a la menos 21, un nivel de precisión que es efectivamente perfecto para casi cualquier aplicación práctica.

Los resultados de este trabajo no son solo un ejercicio teórico; proporcionan una herramienta concreta y fiable para científicos e ingenieros que necesitan comprender el comportamiento de sistemas complejos. Al demostrar que pueden encontrar y certificar millones de ceros con absoluta certeza, los investigadores han eliminado una barrera significativa en la matemática computacional. Su método no depende de la suerte o la aproximación; utiliza una combinación de información global sobre la función y refinamiento local para asegurar que la respuesta sea correcta. El código que desarrollaron está abierto para que cualquiera lo use, permitiendo que otros apliquen esta poderosa técnica a sus propios problemas. En un campo donde perder un solo cero puede conducir a conclusiones incorrectas sobre la estabilidad de un puente o la distribución de los números primos, esta capacidad de encontrar cada uno de ellos con tal alto nivel de confianza representa un paso significativo hacia adelante en cómo resolvemos estos difíciles acertijos matemáticos.

Resumen Técnico: Un Algoritmo Paralelo Adaptativo para el Cálculo de Ceros de Funciones Analíticas

Planteamiento del Problema
El artículo aborda el desafío de calcular de manera robusta y eficiente los ceros de funciones analíticas dentro de una región rectangular especificada en el plano complejo. Si bien la búsqueda de raíces para ecuaciones no lineales es un problema fundamental en la física, la ingeniería y las matemáticas, los métodos estándar suelen tener dificultades con la convergencia global o no logran proporcionar resultados certificados para funciones con comportamientos complejos, como los polinomios exponenciales y los polinomios de Dirichlet. Específicamente, los autores señalan que los valores finitos de una función y sus derivadas son insuficientes para determinar el número de ceros en una región acotada sin datos globales, y que la discretización de contornos para el conteo de argumentos requiere un manejo cuidadoso para evitar omitir ceros o acumular errores de redondeo.

Metodología
El algoritmo propuesto integra cuatro componentes distintos para asegurar la robustez, la convergencia y la velocidad:

Conteo de Argumento Adaptativo (Información Global):
El núcleo del procedimiento de conteo de ceros se basa en el Principio del Argumento. Para calcular la variación del argumento a lo largo de una trayectoria, los autores adaptan un criterio derivado de Ying y Katz. Este método discretiza el contorno en segmentos donde se garantiza que la variación del argumento sea menor que $\pi$ .
- Mecanismo: Para un segmento $[s_1, s_2]$ , la función $f(s)$ se aproxima mediante una función afín $P(s)$ . El algoritmo asegura que el módulo mínimo de $P(s)$ supere el límite de error máximo del resto $R(s) = f(s) - P(s)$ .
- Límites de Error: El límite de error se deriva de una cota sobre la segunda derivada, $|f''(s)| \le M(s_1, s_2)$ , mediante un lema de error de interpolación corregido.
- Adaptatividad: Se emplea una búsqueda de línea de retroceso (backtracking) adaptativa. Si la condición para la variación del argumento no se cumple (por ejemplo, debido a un cero cercano o un límite laxo), el segmento se subdivide. Esto evita la necesidad de una discretización fija a priori y gestiona regiones donde el argumento varía rápidamente.
Estrategia de Bisección Bidimensional:
Una vez determinado el número de ceros en un rectángulo, el algoritmo subdivide la región recursivamente para aislar ceros individuales.
- El rectángulo se divide mediante la bisección de su lado más largo.
- Para manejar ceros que se encuentran sobre o cerca del límite de subdivisión, el algoritmo perturba el segmento de subdivisión y vuelve a calcular la variación del argumento, asegurando que no haya ceros en los límites de los sub-rectángulos resultantes.
- Este proceso produce una colección de rectángulos de tamaño equilibrado, cada uno de los cuales contiene exactamente un cero simple, con diámetros que convergen linealmente a cero.
Criterio de Exclusión:
Para mejorar la eficiencia, el algoritmo emplea un criterio de exclusión basado en la fórmula de Taylor. Para un rectángulo $R$ con centro $z_0$ y radio $r$ , si la desigualdad $|f(z_0)| - |f'(z_0)|r - \frac{1}{2}N(z_1, z_2)r^2 > 0$ se cumple (donde $N$ acota la segunda derivada), el rectángulo se descarta por no contener ceros. Este paso es opcional pero reduce significativamente el espacio de búsqueda.
Aceleración y Certificación (Newton–Kantorovich):
Dado que el método de bisección converge linealmente, el algoritmo acelera la etapa final utilizando el método de Newton.
- Una vez que un rectángulo ha aislado un único cero, se aplica el método de Newton partiendo del centro del rectángulo.
- Certificación: La convergencia se certifica utilizando el teorema de Kantorovich. El algoritmo verifica condiciones que involucran la inversa de la derivada y la cota de la segunda derivada para garantizar que existe una solución única dentro de un radio específico y que el método de Newton convergerá hacia ella.
- Convergencia Global: Si el método de Newton falla (por ejemplo, diverge o excede los límites de iteración), el algoritmo revierte al método de bisección sobre el rectángulo actual, asegurando la convergencia global.

Implementación y Paralelización
El algoritmo está implementado en C++ utilizando las librerías Boost para aritmética de multiprecisión.

Arquitectura Paralela: La subdivisión del rectángulo inicial crea subproblemas independientes. La implementación utiliza un enfoque basado en una pila donde los procesadores disponibles extraen rectángulos de una pila protegida por un mutex.
Seguridad de Hilos (Thread Safety): Los mutex protegen la pila de tareas y la pila de "respuestas" (donde se almacenan los ceros certificados) para prevenir condiciones de carrera.
Precisión: El uso de librerías de multiprecisión permite al algoritmo manejar la alta precisión requerida para funciones como las sumas parciales de la función zeta de Riemann.

Resultados Clave
Los autores aplicaron el algoritmo a dos clases específicas de funciones:

Polinomios Exponenciales: Estos surgen en ecuaciones diferenciales con retardo y exhiben tipos asintóticos retardados, avanzados y neutros. El algoritmo calculó con éxito los ceros para una función de prueba que exhibía los tres tipos.
Polinomios de Dirichlet (Sumas Parciales de la Función Zeta de Riemann): El benchmark principal consistió en calcular los ceros de las sumas parciales $\zeta_n(s) = \sum_{k=1}^n k^{-s}$ $ζ_{n} (s) = \sum_{k = 1}^{n} k^{- s}$ para $3 \le n \le 26$ $3 \leq n \leq 26$ .
- Escala: El estudio calculó más de 2.5 millones de ceros certificados.
- Tolerancia: Todos los resultados se calcularon dentro de una tolerancia garantizada de $9.9 \times 10^{-21}$ .
- Rendimiento: Las pruebas de rendimiento se realizaron en un sistema AMD Ryzen 9 de 24 hilos. Por ejemplo, calcular los ceros para $n=26$ con partes imaginarias hasta $100,000$ tomó aproximadamente 6,711 segundos. El artículo señala que el parámetro $\rho$ (que controla la reducción de pasos en la búsqueda adaptativa) impacta significativamente el tiempo de ejecución, con valores óptimos que varían según la instancia del problema.

Significancia y Reivindicaciones
El artículo afirma proporcionar un método robusto y certificado para la búsqueda de ceros que supera las limitaciones de los métodos puramente locales (como la iteración de Newton estándar) y los métodos puramente globales que pueden ser computacionalmente costosos.

Robustez: Al combinar el conteo de argumentos global con el refinamiento local, el método asegura que no se omitan ceros y que los resultados estén matemáticamente certificados mediante el teorema de Kantorovich.
Eficiencia: La naturaleza adaptativa del conteo de argumentos y la estrategia de bisección paralela permiten que el método escale a millones de ceros.
Aplicabilidad: El método es particularmente efectivo para polinomios exponenciales y de Dirichlet, donde las cotas sobre las derivadas pueden derivarse explícitamente, aunque los autores reconocen que el requisito de las cotas de las derivadas es una condición necesaria para la robustez de su enfoque específico.

Los autores enfatizan que su contribución radica en la síntesis de estos cuatro componentes (conteo, subdivisión, exclusión y refinamiento) en un marco único y paralelizable que entrega resultados de alta precisión y certificados para funciones analíticas complejas.

Resumen Técnico: Un Algoritmo Paralelo Adaptativo para el Cálculo de Ceros de Funciones Analíticas

Más como este