计算机科学

首页 > 计算机科学

欧德里兹科-肖恩哈格算法

2018-08-28 09:44:01     所属分类:计算数论

在数学中,欧德里兹科-肖恩哈格算法是一个用于评估多点上黎曼ζ函数的值的快速算法,由( Odlyzko & Schönhage 1988)发现。其主要思想是使用快速傅里叶变换加速N个等O(N)间隔的值的有限狄利克雷级数的计算,从O(N2)步减少到O(N1+ε)步(花费存储O(N1+ε)个中间值的代价)。黎曼-西格尔公式,用于计算虚部为T点上黎曼ζ函数的值,使用约N = T1/2项的有限狄利克雷级数,所以要找到N个黎曼ζ函数的值时,它将加速约T1/2倍。这将找到虚部不超过T的ζ函数零点所需的时间从大约T3/2+ε步减少到了大约T1+ε步。

该算法不仅可以用于黎曼ζ函数,还可以用于狄利克雷级数给出的许多其他函数。

该算法被Gourdon (2004)用于验证黎曼猜想ζ函数的前1013个零点。

参考

  • Gourdon, X., Numerical evaluation of the Riemann Zeta-function 
  • Gourdon, The 1013 first zeros of the Riemann Zeta function, and zeros computation at very large height, 2004 
  • Odlyzko, A., The 1020-th zero of the Riemann zeta function and 175 million of its neighbors, 1992 这本未发表的书描述了算法的实现,并详细讨论了结果。
  • 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 

上一篇:格规约
相关推荐