On the Parallel Evaluation of Multivariate Polynomials
Author:
- Laurent HyafilLHLaurent Hyafil
- 1 May 1979
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 8 (2) , 120-123
Abstract
We prove that any multivariate polynomial P of degree d that can be computed with $C(P)$ multiplications-divisions can be computed in $O(\log d \cdot \log C(P))$ parallel steps and $O(\log d)$ parallel multiplicative steps.
Keywords
This publication has 2 references indexed in Scilit:
- The power of commutativity1977
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976