A fast algorithm for repeated computation of linear recurrence relations

Let the calculation of thenth term of a general recurrence relation requireO(q(n)) arithmetical operations. The derivation is given of a new algorithm that performsm repetitions of this calculation with different initial conditions requiring onlyO(q(n)) +O(m) operations. The application of this algorithm to accelerate the calculation of continued fractions and the solution of three- and five-diagonal systems of linear equations, is also described.