Theoretical Computer Science
dc.parallel-comp recursion
Updated Sat, 28 May 2022 06:36:53 GMT

Parallel solution of recurrence equation


One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the form:

$x_{1}=b_{1}$
$x_{i}=f_{i}(x_{i-1})=f(b_{i},g(a_{i},x_{i-1}))$

can be solved if the following restrictions are satisfied:
1) $f$ is associative, $f(x,f(y,z))=f(f(x,y),z)$
2) $g$ distributes over $f$, $g(x,f(y,z))=f(g(x,y),g(x,z))$
3) $g$ is semiassociative, that is, there exists some function $h$ such that $g(x,g(y,z))=g(h(x,y),z)$.

Question: Are there any other general algorithms that can solve some class of recurrence equations in parallel?




Solution

For linear recurrences, you may find interesting this recent work:

Adrian Nistor, Wei-Ngan Chin, Tiow-Seng Tan, and Nicolae Tapus. 2009. Optimizing the parallel computation of linear recurrences using compact matrix representations. J. Parallel Distrib. Comput. 69, 4 (April 2009), 373-381. DOI=10.1016/j.jpdc.2009.01.004 http://dx.doi.org/10.1016/j.jpdc.2009.01.004

A discussion of the parallel complexity of solving recurrences is available in

Oscar H. Ibarra and Nicholas Q. Tr\ân. 1994. On the Parallel Complexity of Solving Recurrence Equations. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC '94), Ding-Zhu Du and Xiang-Sun Zhang (Eds.). Springer-Verlag, London, UK, 469-477.

Hope this helps.