Fast Parallel Computation of Polynomials Using Few Processors
Authors:
- L. G. ValiantLVL. G. Valiant
- S. SkyumSSS. Skyum
- S. BerkowitzSBS. Berkowitz
- C. RackoffCRC. Rackoff
- 1 November 1983
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 12 (4) , 641-644
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)(\log C + \log d))$ steps using only $(Cd)^{O(1)} $ processors.
Keywords
This publication has 9 references indexed in Scilit:
- Fast parallel matrix and GCD computations1982
- Some Exact Complexity Results for Straight-Line Computations over SemiringsJournal of the ACM, 1982
- On the asymptotic complexity of matrix multiplication1981
- A complexity theory based on Boolean algebra1981
- Fast parallel computation of polynomials using few processorsLecture Notes in Computer Science, 1981
- On uniform circuit complexity1979
- Completeness classes in algebra1979
- On the parallel evaluation of multivariate polynomials1978
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976