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

Martin Ziegler

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_1],...,P[n_L], both for the…