“A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations”, 1973-08 ():
An mth-order recurrence problem is defined as the computation of the series x1, x2, …, XN, where xi = fi(xi−1, …, xi−m) for some function fi.
This paper uses a technique called recursive doubling in an algorithm for solving a large class of recurrence problems on parallel computers such as the ILLIAC IV [cf. prefix sum]. Recursive doubling involves the splitting of the computation of a function into two equally complex sub-functions whose evaluation can be performed simultaneously in two separate processors. Successive splitting of each of these sub-functions spreads the computation over more processors.
The resulting algorithm computes the entire series x1, …, xN in time proportional to 𝒪(log2 n) on a computer with N-fold parallelism. On a serial computer, computation time is proportional to N.
This algorithm can be applied to any recurrence equation of the form xi = f(bi, g(ai, xi−1)) where f and g are functions that satisfy certain distributive and associative-like properties. Although this recurrence is first order, all linear mth-order recurrence equations can be cast into this form. Suitable applications include linear recurrence equations, polynomial evaluation, several nonlinear problems, the determination of the maximum or minimum of N numbers, and the solution of tridiagonal linear equations.