Algorithme d'Odlyzko-Schönhage

En mathématiques, l'algorithme d'Odlyzko-Schönhage est un algorithme d'évaluation rapide de la fonction zêta de Riemann

$\zeta ~:~z\mapsto \sum _{n=1}^{ \infty }{\frac {1}{n^{z}}}$.

Cet algorithme, présenté en 1988 par Andrew Odlyzko et Arnold Schönhage, a servi au premier auteur dans le calcul du 10²⁰-ème zéro et de valeurs proches de la fonction zêta de Riemann, dans le cadre de la vérification de la conjecture connue sous le nom d'hypothèse de Riemann.

L'aspect principal de l'algorithme est l'usage de la transformation de Fourier rapide pour accélérer l’évaluation simultanée d'une série de Dirichlet finie de N termes en O(N) points également distribués, qui passe d'une complexité en temps de O(N²) à O(N^{1 ε}), sous réserve de stocker O(N^{1 ε}) valeurs intermédiaires. La formule de Riemann–Siegel utilisée pour calculer la fonction zêta de Riemann avec partie imaginaire T utilise une série de Dirichlet finie avec environ N = T^1/2 termes, de sorte que la complexité en temps pour trouver autour de N valeurs de la fonction zêta de Riemann est accélérée d'un facteur autour de T^1/2. Ceci réduit le temps pour trouver les zéros de la fonction zêta de Riemann avec partie imaginaire au plus T de T^{3/2 ε} à environ T^{1 ε} étapes.

L'algorithme a été repris plus tard par Xavier Gourdon et Patrick Demichel qui ont poussé les calculs plus loin encore.

L'algorithme peut servir non seulement pour la fonction zêta de Riemann, mais aussi pour beaucoup d'autres fonctions données par des séries de Dirichlet.

Bibliographie

• Xavier Gourdon, « Numerical evaluation of the Riemann Zeta-function », 2003
• Xavier Gourdon, « The 10¹³ first zeros of the Riemann Zeta function, and zeros computation at very large height », 2004
• Andrew M. Odlyzko, « The 10²⁰-th zero of the Riemann zeta function and 175 million of its neighbors », 1992. — Ce document, de 120 pages est resté inédit. Il décrit l'algorithme, son implémentation et les résultats en détail.
• Andrew M. Odlyzko et Arnold Schönhage, « Fast algorithms for multiple evaluations of the Riemann zeta function », Trans. Amer. Math. Soc., vol. 309, n^o 2,‎ 1988, p. 797–809 (DOI 10.2307/2000939, JSTOR 2000939, MR 0961614)