Fast (Multi-)Evaluation of Linearly Recurrent Sequences: Improvements and Applications

Original · EN

For a linearly recurrent vector sequence P[n+1] = A(n) * P[n], consider the problem of calculating either the n-th term P[n] or L<=n arbitrary terms P[n₁],...,P[nₗ], both for the case of constant coefficients A(n)=A and for a matrix A(n) with entries polynomial in n. We improve and extend known algorithms for this problem and present new applications for it. Specifically it turns out that for instance * any family (pₙ) of classical orthogonal polynomials admits evaluation at given x within O(n¹/² log n) operations INDEPENDENT of the family (pₙ) under consideration. * For any L indices n₁,...,nₗ <= n, the values pₙᵢ(x) can be calculated simultaneously using O(n¹/² log n + L log(n/L)) arithmetic operations; again this running time bound holds uniformly. * Every hypergeometric (or, more generally, holonomic) function admits approximate evaluation up to absolute error e>0 within O((log(1/e)¹/² loglog(1/e)) -- as opposed to O(log(1/e)) -- arithmetic steps. * Given m and a polynomial p of degree d over a field of characteristic zero, the coefficient of pᵐ to term Xⁿ can be computed within O(d² M(n¹/²)) steps where M(n) denotes the cost of multiplying two degree-n polynomials. * The same time bound holds for the joint calculation of any L<=n¹/² desired coefficients of pᵐ to terms Xⁿⁱ, n₁,...,nₗ <= n.