Algoritme van Odlyzko-Schönhage

In de getaltheorie, een deelgebied van de wiskunde, is het algoritme van Odlyzko-Schönhage een snel algoritme voor het evalueren van de Riemann-zèta-functie op veel punten. Het algoritme werd in 1988 geïntroduceerd door Andrew Odlyzko en Arnold Schönhage. Het belangrijkste aspect is het gebruik van snelle fourier-transformaties om de evaluatie van eindige Dirichletreeksen van lengte $N$ op een aantal van $O(N)$ gelijkelijk verdeelde waarden te versnellen van $O(N^{2})$ tot $O(N^{1+\varepsilon })$ stappen (overigens wel ten koste van het opslaan van $O(N^{1+\varepsilon })$ tussenresultaten).

De Riemann-Siegel-formule, die wordt gebruikt voor de berekening van de Riemann-zèta-functie met imaginair deel T maakt gebruik van een eindige Dirichletreeks met ongeveer $N=T^{1/2}$ termen, dus bij het vinden van ongeveer $N$ waarden van de Riemann-zèta-functie wordt de berekening met een factor van ongeveer $N=T^{1/2}$ versneld. Dit vermindert de tijd om de nulpunten van de zèta-functie met imaginaire deel op ten hoogste $T$ te berekenen van ongeveer $T^{3/2+\varepsilon }$ stappen naar ongeveer $N=T^{1+\varepsilon }$ stappen.

Het algoritme kan niet alleen worden gebruikt voor de Riemann-zèta-functie, maar ook voor vele andere functies die worden gegeven door de Dirichlet-reeksen.

Het algoritme werd gebruikt door Gourdon (2004) om te Riemann-hypothese voor de eerste 10¹³ nulpunten van de Riemann-zèta-functie te verifiëren.

Referenties

• X. Gourdon, Numerical evaluation of the Riemann Zeta-function
• X. Gourdon, The 10¹³ first zeros of the Riemann Zeta function, and zeros computation at very large height, 2004
• A. Odlyzko, The 10²⁰-th zero of the Riemann zeta function and 175 million of its neighbors, 1992, [1] (dit ongepubliceerde boek beschrijft de implementatie van het algoritme en de resultaten in detail).
• A.M. Odlyzko, A. Schönhage, Fast algorithms for multiple evaluations of the Riemann zeta function, Trans. Amer. Math. Soc., volume 309, 1988, issue 2, blz. 797–809