Fast (Multi-)Evaluation of Linearly Recurrent Sequences: Improvements and Applications
Martin Ziegler · arXiv (Cornell University) · 2005
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 L0 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 p^m to term X^n can be computed within O(d^2 M(n^{1/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<=n^{1/2} desired coefficients of p^m to terms X^{n_i}, n_1,...,n_L <= n.