ALGEBRAIC RECURRENCE TRANSFORMATIONS FOR MASSIVE PARALLELISM

If an algorithm needs to be implemented for a high-speed application, a recursive loop is often found to be a bottleneck. Therefore, for some practical examples much work has been done so far to show how to transform single-step recursions into M-step recursions using so-called ''look-ahead computations.'' In this paper, we show that certain algebraic structures are sufficient for the operations of the loop, to allow the application of the well-knwn look-ahead computation. This provides a unifying algebraic basis to derive a new generalization for more complex recursions with more than one operation, which now allows the application of look-ahead computation to a wide area of problems.