×

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