基本介紹
- 中文名：歐德里茲科-肖恩哈格算法
- 外文名：Odlyzko–Schönhage algorithm
簡介,黎曼ζ函式,黎曼猜想,
簡介
在數學中，歐德里茲科-肖恩哈格算法是一個用於評估多點上黎曼ζ函式的值的快速算法，由(Odlyzko&Schönhage1988)發現。其主要思想是使用快速傅立葉變換加速N個等O(N)間隔的值的有限狄利克雷級數的計算，從O(N2)步減少到O(N1+ε)步（花費存儲O(N1+ε)箇中間值的代價）。黎曼-西格爾公式，用於計算虛部為T點上黎曼ζ函式的值，使用約N=T1/2項的有限狄利克雷級數，所以要找到N個黎曼ζ函式的值時，它將加速約T1/2倍。這將找到虛部不超過T的ζ函式零點所需的時間從大約T3/2+ε步減少到了大約T1+ε步。
該算法不僅可以用於黎曼ζ函式，還可以用於狄利克雷級數給出的許多其他函式。該算法被Gourdon (2004)用於驗證黎曼猜想ζ函式的前10個零點。
黎曼ζ函式
在區域{s: Re(s) > 1}上，此無窮級數收斂並為一全純函式（其中Re表示複數的實部，下同）。歐拉在1740考慮過s為正整數的情況，後來切比雪夫拓展到s>1。波恩哈德·黎曼認識到：ζ函式可以通過解析開拓來擴展到一個定義在複數域（s,s≠ 1）上的全純函式ζ（s）。這也是黎曼猜想所研究的函式。
雖然黎曼的ζ函式被數學家認為主要和“最純”的數學領域數論相關，它也出現在套用統計學（參看齊夫定律（Zipf's Law）和齊夫-曼德爾布羅特定律（Zipf-Mandelbrot Law））、物理，以及調音的數學理論中。
