<p>For linear recurrences, you may find interesting this recent work:</p>

<p>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 <a href="http://dx.doi.org/10.1016/j.jpdc.2009.01.004">http://dx.doi.org/10.1016/j.jpdc.2009.01.004</a></p>

<p>A discussion of the parallel complexity of solving recurrences is available in</p>

<p>Oscar H. Ibarra and Nicholas Q. Tr\&amp;#226;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.</p>

<p>Hope this helps.</p>

CC BY-SA 3.0
2011-05-26T19:32:07.163Z
2011-05-26T19:32:07.163Z
Massimo Cafaro
<p>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 <a href="http://bwrc.eecs.berkeley.edu/classes/ee225c/2000%20225c/Papers/KoggeStone.pdf" rel="nofollow">here</a>). They proved that all recurrence equations of the form:</p>

<p>$x_{1}=b_{1}$<br>
$x_{i}=f_{i}(x_{i-1})=f(b_{i},g(a_{i},x_{i-1}))$</p>

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

<p><strong>Question</strong>: Are there any other general algorithms that can solve some class of recurrence equations in parallel?</p>

CC BY-SA 2.5
2011-01-30T13:31:40.197Z
link is not available? but if it's an if and only if theory there is no other way and I think it should be if and only if.
Saeed
CC BY-SA 2.5
2011-01-30T13:58:49.963Z
link fixed. Tomek, can you explain what is 'efficiently parallel' here ?
Suresh Venkat
CC BY-SA 2.5
2011-01-30T15:50:31.680Z
@Tomek: yes. Parallel Algorithms for Knapsack Type Problems by Aleksandrov is one book that deals with this.
Aaron Sterling
CC BY-SA 2.5
2011-01-31T09:39:21.573Z
@Suresh: I think that the word 'efficiently' in this context means that it is the fastest possible algorithm. Since this problem involves summing n numbers in parallel it can't be done faster than $O(logn)$ using $O(n)$ processors and that is the complexity of this algorithm.
Tomek Tarczynski
CC BY-SA 2.5
2011-01-31T09:41:35.907Z
@Aaron: Thanks for the book, it seems to be good, but unfortunatelly only half of it is available in google books and it'll take me some time till I find hardcopy.
Tomek Tarczynski
CC BY-SA 2.5
2011-01-31T17:01:44.693Z
@Aaron, make the comment an answer ?
Suresh Venkat
<dc.parallel-comp><recursion>
Parallel solution of recurrence equation
Tomek Tarczynski
# Parallel solution of recurrence equation

(Asked by: username_0 on 2011-01-30)

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](http://bwrc.eecs.berkeley.edu/classes/ee225c/2000%20225c/Papers/KoggeStone.pdf)). 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?

**Tags:** dc.parallel-comp, recursion
> **Comments:**
> **username_1**: link is not available? but if it's an if and only if theory there is no other way and I think it should be if and only if.  
> **username_2**: link fixed. Tomek, can you explain what is 'efficiently parallel' here ?  
> **username_3**: @Tomek: yes. Parallel Algorithms for Knapsack Type Problems by Aleksandrov is one book that deals with this.  
> **username_0**: @Suresh: I think that the word 'efficiently' in this context means that it is the fastest possible algorithm. Since this problem involves summing n numbers in parallel it can't be done faster than $O(logn)$ using $O(n)$ processors and that is the complexity of this algorithm.  
> **username_0**: @Aaron: Thanks for the book, it seems to be good, but unfortunatelly only half of it is available in google books and it'll take me some time till I find hardcopy.  
> **username_2**: @Aaron, make the comment an answer ?  

---

## 1 answers

### Answer by username_4 on 2011-05-26. Score: 6 | Accepted answer

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.


---

