<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. username_0, can you explain what is 'efficiently parallel' here ?  
> **username_3**: @username_0: yes. Parallel Algorithms for Knapsack Type Problems by Aleksandrov is one book that deals with this.  
> **username_0**: @username_2: 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**: @username_3: 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**: @username_3, 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\&#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.

Hope this helps.


---

