Fast Parallel Computation of Polynomials Using Few Processors

Abstract

It is shown that any multivariate polynomial of degree d that can be computed sequentially in C steps can be computed in parallel in O((log d)(logC+ log d)) steps using only (Cd) 1) processors. Introduction. Hyafil (6) showed that any polynomial q of degree d that can be computed sequentially in C {+,-, x}-steps can be computed in parallel in time proportional to (log d)(logC+log d). Unfortunately his method requires C ga pro- cessors in general. Thus even if C and d are both bounded polynomially in terms of the number of indeterminates the number of processors required would not be. In this paper we give an improved construction that achieves the same time bound but with only (Cd) processors, for an appropriate constant//. The achievability of such fast time bounds with only polynomially many processors was known previously only for certain specific polynomials such as the determinant (5). Throughout we shall use the unrestricted model of parallelism described by Borodin and Munro (2).