FAST COMPUTATION OF SOLUTIONS OF LINEAR DIFFERENCE-EQUATIONS BY ERS RULE

An efficient algorithm for computing the n-th element of the solution of a linear difference equation is presented in this paper. This algorithm uses only O(k2 log(n/k)) time and O(k) space for performing the task. When n < 3k, the time complexity of the algorithm is improved to O(kn). A matrix representation of k sequences of solutions of k linear difference equations is used. It turns out that only a row of the matrix needs to be explicitly represented, as other rows of the matrix can be derived from this row when needed. Furthermore, Er's rule is used for guiding the recursive chain of matrix multiplications. In this algorithm is superior than the previously published algorithms for performing the same task.