Fast Algorithms for Multiple Evaluations of the Riemann Zeta Function

The best currently known algorithm for evaluating the Riemann zeta function integral(sigma+it), with a sigma bounded and t large to moderate accuracy (within plus t-c for some c > 0, say) is based on the Riemann-Siegel formula and requires on the order of t 1/2 operations for each value that is computed. New algorithms are presented in this paper which enable one to compute any single value of integral (sigma+ it) with integral fixed and T less than t less than T+T1/2 to within minus t-c in O (t epsilon) operations on numbers of O (log t) bits for any epsilon >0. for example, provided a precomputation involving O(T1/2+epsilon) operations and O(T1/2+epsilon) bits of storage is carried out beforehand.