# zbMATH — the first resource for mathematics

Parallel algorithms for solving certain classes of linear recurrences. (English) Zbl 0593.68029
Foundations of software technology and theoretical computer science, Proc. 5th Conf., New Delhi/India 1985, Lect. Notes Comput. Sci. 206, 457-476 (1985).
Summary: [For the entire collection see Zbl 0578.00011.]
This paper presents two new time and/or procesor bounds for solving certain classes of linear recurrences. The first result provides a parallel algorithm for solving $$X_ i=a_ iX_{i-1}+d_ i$$ for $$1\leq i\leq n$$ in 2 log n units of time using only 3/4n processors. The second results relate to solving $$X_ i=X_{i-1}+X_{i-2}+d_ i$$ for $$1\leq i\leq n$$. It is shown that $$X_ i's$$ can be computed in at most 3 log n units of time using 5/4n processors. In the special case when $$d_ i=0$$ for all i, it is shown that $$X_ i's$$ (the first n-Fibonacci numbers) can be computed in parallel in 2 log n-1 units of time using only n/2 processors. These time and processor bounds compare very favourably with the previously known results for these problems.

##### MSC:
 68W30 Symbolic computation and algebraic computation 68Q25 Analysis of algorithms and problem complexity 11B37 Recurrences
##### Keywords:
time bounds; procesor bounds