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 ${\displaystyle N}$ op een aantal van ${\displaystyle O(N)}$ gelijkelijk verdeelde waarden te versnellen van ${\displaystyle O(N^{2})}$ tot ${\displaystyle O(N^{1+\varepsilon })}$ stappen (overigens wel ten koste van het opslaan van ${\displaystyle 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 ${\displaystyle N=T^{1/2}}$ termen, dus bij het vinden van ongeveer ${\displaystyle N}$ waarden van de Riemann-zèta-functie wordt de berekening met een factor van ongeveer ${\displaystyle N=T^{1/2}}$ versneld. Dit vermindert de tijd om de nulpunten van de zèta-functie met imaginaire deel op ten hoogste ${\displaystyle T}$ te berekenen van ongeveer ${\displaystyle T^{3/2+\varepsilon }}$ stappen naar ongeveer ${\displaystyle 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.

• 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