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[1], présenté en 1988 par Andrew Odlyzko et Arnold Schönhage, a servi au premier auteur[2] 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[3] et Patrick Demichel qui ont poussé les calculs plus loin encore[4].

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.

Notes et références

Odlyzko et Schönhage 1988.
Odlyzko, « The 10²⁰-th zero of the Riemann zeta function » 1992.
Gourdon, « Numerical evaluation of the Riemann Zeta-function » 2003.
Gourdon et Demichel, « The 10¹³ first zeros of the Riemann Zeta function » 2004.

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, Math Reviews 0961614)

Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Odlyzko et Schönhage 1988.

[2] Odlyzko, « The 10²⁰-th zero of the Riemann zeta function » 1992.

[3] Gourdon, « Numerical evaluation of the Riemann Zeta-function » 2003.

[4] Gourdon et Demichel, « The 10¹³ first zeros of the Riemann Zeta function » 2004.