2005/11/08 by Martin Ziegler, Ziegler, Martin
Computer Science · #Digital Filter Design and Implementation #FOS: Computer and information sciences #Numerical Methods and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC
paper · pdf · doi:10.48550/arxiv.cs/0511033
arxiv created 2005/11/08 · openalex publication_date 2005/11/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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[n1],...,P[nL], 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 (pn) of classical orthogonal polynomials admits evaluation at given x within O(n1/2 log n) operations INDEPENDENT of the family (pn) under consideration. * For any L indices n1,...,nL <= n, the values pni(x) can be calculated simultaneously using O(n1/2 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)1/2 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 pm to term Xn can be computed within O(d2 M(n1/2)) 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<=n1/2 desired coefficients of pm to terms Xni, n1,...,nL <= n.