Algoritme van Odlyzko-Schönhage

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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 op een aantal van gelijkelijk verdeelde waarden te versnellen van tot stappen (overigens wel ten koste van het opslaan van 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 termen, dus bij het vinden van ongeveer waarden van de Riemann-zèta-functie wordt de berekening met een factor van ongeveer versneld. Dit vermindert de tijd om de nulpunten van de zèta-functie met imaginaire deel op ten hoogste te berekenen van ongeveer stappen naar ongeveer 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 | brontekst bewerken]