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

@article{Kogge1973APA, title={A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations}, author={Peter M. Kogge and Harold S. Stone}, journal={IEEE Transactions on Computers}, year={1973}, volume={C-22}, pages={786-793} }

An mth-order recurrence problem is defined as the computation of the series x<inf>1</inf>, x<inf>2</inf>, ..., X<inf>N</inf>, where x<inf>i</inf> = f<inf>i</inf>(x<inf>i-1</inf>, ..., x<inf>i-m</inf>) for some function f<inf>i</inf>. 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… Expand

#### 1,233 Citations

Time and Parallel Processor Bounds for Linear Recurrence Systems

- Mathematics, Computer Science
- IEEE Transactions on Computers
- 1975

By a simple transformation, the results can also be applied to the solution of any triangular linear system of equations Ax̄ = b̄, and the computer need only perform one type of operation at each time step. Expand

New algorithms and lower bounds for the parallel evaluation of certain rational expressions

- Mathematics, Computer Science
- STOC '74
- 1974

It is proved that by using parallelism the evaluation of any first order rational recurrence, e.g., [equation], and any <underline>non-linear</underline] polynomial recurrence can be sped up at most by a constant factor, no matter how many processors are used. Expand

Parallel Solution of Recurrence Problems

- Mathematics, Computer Science
- IBM J. Res. Dev.
- 1974

It is shown that if the recurrence function f has associated with it two other functions that satisfy certain composition properties, then it can be constructed elegant and efficient parallel algorithms that can compute all N elements of the series in time proportional to ⌈log2N⌉. Expand

New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences

- Mathematics, Computer Science
- JACM
- 1976

It is shown that by using parallelism the evaluation of any first-order rational recurrence of degree greater than 1 can be sped up at most by a constant factor, no matter how many processors are used and how large the size of the problem is. Expand

K-Dimensional Optimal Parallel Algorithm for the solution of a general class of recurrence equations

- Computer Science
- Journal of Computer Science and Technology
- 2008

This paper proposes a parallel algorithm, called KDOP (K-Dimensional Optimal Parallel algorithm), to solve a general class of recurrence equations efficiently, and can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems. Expand

Parallel Solutions of Simple Indexed Recurrence Equations

- Computer Science
- IEEE Trans. Parallel Distributed Syst.
- 2001

It is shown why efficient parallel algorithms for the related problems of list ranking and tree contraction, which require O(n) work, cannot be applied to solving SIR, and useful applications of SIR to the well-known Livermore loops benchmark are presented. Expand

The power of parallel prefix

- Computer Science
- IEEE Transactions on Computers
- 1985

This study assumes the weakest PRAM model, where shared memory locations can only be exclusively read or written (the EREW model) to solve the prefix computation problem, when the order of the elements is specified by a linked list. Expand

Parallel algorithms

- Computer Science
- CSUR
- 1996

The parallelism in an algorithm can yield improved performance on many di erent kinds of computers, for example, on a parallel computer, the operations in a parallel algorithm can be performed simultaneously by two or more processors. Expand

A chained-matrices approach for parallel computation of continued fractions and its applications

- Mathematics
- 1994

A chained-matrices approach for parallel computing thenth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction inO(logn)… Expand

Prefix algorithms for tridiagonal systems on hypercube multiprocessors

- Computer Science
- C3P
- 1989

A limited processor version of the recursive doubling algorithm for the solution of tridiagonal linear systems using fast parallel prefix algorithms that achieves linear speed-up and constant efficiency over its sequential implementation as well as over the sequential LU decomposition algorithm. Expand

#### References

SHOWING 1-3 OF 3 REFERENCES

An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations

- Computer Science
- JACM
- 1973

An efficient parallel algorithm is presented in which computation time grows as log 2, which can be used to solve recurrence relations of all orders. Expand

Optimal Algorithms for Parallel Polynomial Evaluation

- Computer Science
- J. Comput. Syst. Sci.
- 1973

It is shown that, provided the degree of the polynomial to be evaluated exceeds k[log"2k], an algorithm given is within one time unit of optimality. Expand

Optimal algorithms for paraUel polynomial evaluation

- SIAM J . Numner . Anal .
- 1970