A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations

Publisher Website
Google Scholar
Abstract
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 Iliac IV. Recursive doubling involves the splitting of the computation of a function into two equally complex subfunctions whose evaluation can be performed simultaneously in two separate processors. Successive splitting of each of these subfunctions spreads the computation over more processors. 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. 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 publication has 2 references indexed in Scilit: