Portal de Periódicos da CAPES

Fast Parallel Computation of Polynomials Using Few Processors

1983; Society for Industrial and Applied Mathematics; Volume: 12; Issue: 4 Linguagem: Inglês

10.1137/0212043

1095-7111

Leslie G. Valiant, Sven Skyum, S. J. Berkowitz, Charles Rackoff,

Polynomial and algebraic computation

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)(\log C + \log d))$ steps using only $(Cd)^{O(1)} $ processors.