Algorithme d'Odlyzko-Schönhage

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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 les nom de 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[modifier | modifier le code]

Bibliographie[modifier | modifier le code]