Odlyzko–Schönhage algorithm とは

数学では、Odlyzko-Schönhageアルゴリズムは、(Odlyzko&Schönhage1988)によって導入された多くの点でリーマンゼータ関数を評価するための高速アルゴリズムです。主なポイントは、O(N)からO(N1 +ε)ステップまでの等間隔の値での長さNの有限ディリクレ系列の評価を高速フーリエ変換を使用することです(コストはO(N1 +ε)中間値を記憶する)。 Riemannゼータ​​関数を虚数部Tで計算するために使用されるRiemann-Siegel式は、約N = T1 / 2項の有限ディリクレ系列を使用するので、Riemannゼータ​​関数のN値について求めると、約T1 / 2。これにより、約T3 / 2 +εステップから約T1 +εステップまでの虚数部を有するゼータ関数の零点を見つける時間が短縮される。
このアルゴリズムは、リーマンゼータ関数だけでなく、ディリクレ系列によって与えられる他の多くの関数にも使用できます。
このアルゴリズムはGourdon(2004)がζ関数の最初の1013個の零点に対するリーマン仮説を検証するために使用された。