En matemáticas, el algoritmo Odlyzko-Schönhage es un algoritmo rápido para evaluar la función zeta de Riemann en muchos puntos, introducido por ( Odlyzko & Schönhage 1988 ). El punto principal es el uso de la transformada rápida de Fourier para acelerar la evaluación de una serie de Dirichlet finita de longitud N en O ( N ) valores igualmente espaciados desde O ( N 2 ) a O ( N 1 + ε ) pasos (en el costo de almacenar O ( N 1 + ε ) valores intermedios). La fórmula de Riemann-Siegelutilizado para calcular la función zeta de Riemann con la parte imaginaria T utiliza una serie de Dirichlet finita con aproximadamente N = T 1/2 términos, por lo que cuando se encuentran aproximadamente N valores de la función zeta de Riemann se acelera en un factor de aproximadamente T 1/2 . Esto reduce el tiempo para encontrar los ceros de la función zeta con una parte imaginaria como máximo T desde aproximadamente T 3/2 + ε pasos a aproximadamente T 1 + ε pasos.
El algoritmo se puede utilizar no solo para la función zeta de Riemann, sino también para muchas otras funciones dadas por la serie de Dirichlet.
El algoritmo fue utilizado por Gourdon (2004) para verificar la hipótesis de Riemann para los primeros 10 13 ceros de la función zeta.
Referencias
- Gourdon, X., Evaluación numérica de la función Zeta de Riemann
- Gourdon (2004), Los 10 13 primeros ceros de la función Riemann Zeta y cálculo de ceros a alturas muy grandes
- Odlyzko, A. (1992), El 10 20 -o cero de la función zeta de Riemann y 175 millones de sus vecinas Este libro inédito describe la implementación del algoritmo y analiza los resultados en detalle.
- Odlyzko, AM ; Schönhage, A. (1988), "Algoritmos rápidos para evaluaciones múltiples de la función zeta de Riemann", Trans. Amer. Matemáticas. Soc. , 309 (2): 797–809, doi : 10.2307 / 2000939 , JSTOR 2000939 , MR 0961614