# 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?

• 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 Jan 30 '11 at 13:31
• link fixed. Tomek, can you explain what is 'efficiently parallel' here ? – Suresh Venkat Jan 30 '11 at 13:58
• @Tomek: yes. Parallel Algorithms for Knapsack Type Problems by Aleksandrov is one book that deals with this. – Aaron Sterling Jan 30 '11 at 15:50
• @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 Jan 31 '11 at 9:39
• @Aaron, make the comment an answer ? – Suresh Venkat Jan 31 '11 at 17:01