Algoritme van Odlyzko-Schönhage

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Odlyzko-Schönhage-algoritme)
Ga naar: navigatie, zoeken

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 O(N) gelijkelijk verdeelde waarden te versnellen van O(N2) tot O(N1+ε) stappen (overigens wel ten koste van het opslaan van O(N1+ε) 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 = T1/2 termen, dus bij het vinden van ongeveer N waarden van de Riemann-zèta-functie wordt de berekening met een factor van ongeveer T1/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 T3/2+ε stappen naar ongeveer T1+ε 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 1013 nulpunten van de Riemann-zèta-functie te verifiëren.

Referenties[bewerken]