歐德里茲科-肖恩哈格算法

在數學中，歐德里茲科-肖恩哈格算法是一個用於評估多點上黎曼ζ函數的值的快速算法，由（ Odlyzko & Schönhage 1988）發現。其主要思想是使用快速傅里葉變換加速N個等O(N)間隔的值的有限狄利克雷級數的計算，從O(N²)步減少到O(N^1+ε)步（花費存儲O(N^1+ε)個中間值的代價）。黎曼-西格爾公式，用於計算虛部為T點上黎曼ζ函數的值，使用約N = T^1/2項的有限狄利克雷級數，所以要找到N個黎曼ζ函數的值時，它將加速約T^1/2倍。這將找到虛部不超過T的ζ函數零點所需的時間從大約T^3/2+ε步減少到了大約T^1+ε步。

該算法不僅可以用於黎曼ζ函數，還可以用於狄利克雷級數給出的許多其他函數。

該算法被Gourdon (2004)用於驗證黎曼猜想ζ函數的前10¹³個零點。

參考

• Gourdon, X., Numerical evaluation of the Riemann Zeta-function, [2018-04-13], （原始內容存檔於2018-03-29） 
• Gourdon, The 10¹³ first zeros of the Riemann Zeta function, and zeros computation at very large height, 2004 [2018-04-13], （原始內容存檔於2011-01-15） 
• Odlyzko, A., The 10²⁰-th zero of the Riemann zeta function and 175 million of its neighbors, 1992 [2018-04-13], （原始內容存檔於2018-04-19） 這本未發表的書描述了算法的實現，並詳細討論了結果。
• Odlyzko, A. M.; Schönhage, A., Fast algorithms for multiple evaluations of the Riemann zeta function, Trans. Amer. Math. Soc., 1988, 309 (2): 797–809, JSTOR 2000939, MR 0961614, doi:10.2307/2000939