  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 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_n) of classical orthogonal
polynomials admits evaluation at given x within O(n^{1/2} log n) operations
INDEPENDENT of the family (p_n) under consideration. * For any L indices
n_1,...,n_L <= n, the values p_{n_i}(x) can be calculated simultaneously using
O(n^{1/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 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.

Symbolic Computation