Algorithme d'Odlyzko-Schönhage
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/35px-Racine_carr%C3%A9e_bleue.svg.png)
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En mathématiques, l'algorithme d'Odlyzko-Schönhage est un algorithme d'évaluation rapide de la fonction zêta de Riemann
- .
Cet algorithme[1], présenté en 1988 par Andrew Odlyzko et Arnold Schönhage, a servi au premier auteur[2] dans le calcul du 1020-è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(N2) à O(N1+ε), sous réserve de stocker O(N1+ε) 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 = T1/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 T1/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 T3/2+ε à environ T1+ε é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 1020-th zero of the Riemann zeta function » 1992.
- ↑ Gourdon, « Numerical evaluation of the Riemann Zeta-function » 2003.
- ↑ Gourdon et Demichel, « The 1013 first zeros of the Riemann Zeta function » 2004.
Bibliographie
- Xavier Gourdon, « Numerical evaluation of the Riemann Zeta-function »,
- Xavier Gourdon, « The 1013 first zeros of the Riemann Zeta function, and zeros computation at very large height »,
- Andrew M. Odlyzko, « The 1020-th zero of the Riemann zeta function and 175 million of its neighbors », . — 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, no 2, , p. 797–809 (DOI 10.2307/2000939, JSTOR 2000939, MR 0961614)
Portail des mathématiques
Portail de l'informatique théorique