Brontekst bekijken van 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 [[fast Fourier transform|snelle fourier-transformatie]]s om de evaluatie van eindige [[Dirichletreeks]]en van lengte <math>N</math> op een aantal van <math>O(N)</math> gelijkelijk verdeelde waarden te versnellen van <math>O(N^2)</math> tot <math>O(N^{1+\varepsilon})</math> stappen (overigens wel ten koste van het opslaan van <math>O(N^{1+\varepsilon})</math> tussenresultaten).

De [[Riemann-Siegel-formule]], die wordt gebruikt voor de berekening van de Riemann-zèta-functie met [[imaginair getal|imaginair]] deel ''T'' maakt gebruik van een eindige [[Dirichletreeks]] met ongeveer <math>N=T^{1/2}</math> termen, dus bij het vinden van ongeveer <math>N</math> waarden van de Riemann-zèta-functie wordt de berekening met een factor van ongeveer <math>N=T^{1/2}</math> versneld. Dit vermindert de tijd om de nulpunten van de zèta-functie met imaginaire deel op ten hoogste <math>T</math> te berekenen van ongeveer <math>T^{3/2+\varepsilon}</math> stappen naar ongeveer <math>N=T^{1+\varepsilon}</math> 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<sup>13</sup> nulpunten van de Riemann-zèta-functie te verifiëren.

==Referenties==
*{{aut|X. Gourdon}}, [http://numbers.computation.free.fr/Constants/Miscellaneous/zetaevaluations.html Numerical evaluation of the Riemann Zeta-function]
*{{aut|X. Gourdon}}, [http://numbers.computation.free.fr/Constants/Miscellaneous/zetazeroscompute.html The 10<sup>13</sup> first zeros of the Riemann Zeta function, and zeros computation at very large height], 2004
*{{aut|A. Odlyzko}}, The 10<sup>20</sup>-th zero of the Riemann zeta function and 175 million of its neighbors, 1992, [http://www.dtc.umn.edu/~odlyzko/unpublished/index.html] (dit ongepubliceerde boek beschrijft de implementatie van het algoritme en de resultaten in detail).
*{{aut|A.M. Odlyzko}}, {{aut|A. Schönhage}}, Fast algorithms for multiple evaluations of the Riemann zeta function, [[Transactions of the American Mathematical Society|Trans. Amer. Math. Soc.]], volume 309, 1988, issue 2, blz. 797–809

[[Categorie:Getaltheorie]]