A Simple Parallel Algorithm for Polynomial Evaluation
Lei Li, Jie Hu, Tadao Nakamura · SIAM Journal on Scientific Computing · 1996
In this paper, we show a simple parallel algorithm for polynomial evaluation. By this method, we only need ${{2N} / p} + \log _2 p$ steps on p processors (where $p \leqslant O(N^{{1 / 2}} )$) to evaluate a polynomial of degree N on an SIMD computer or an MIMD computer, which is a decrease of $\log _2 p$ steps as compared with the p-order Homer method [S. Lakshmivarahan and S. K. Dhall, Analysis and Design of Parallel Algorithms, McGraw-Hill, New York, 1990], and also a decrease of $(2\log _2 p)^{{1 / 2}} $ steps as compared with some other algorithms on an MIMD computer [J. I. Munro and M. Paterson, J. Comput. System Sci., 7 (1973), pp. 189–198, K. Maruyama, IEEE Trans. Comput., C-22 (1973), pp. 2–5]. The new algorithm is simple in structure and easy to implement.