Algorithme d'Odlyzko-Schönhage
# 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^{20}-è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^2)$ à $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.

