Very Fast Parallel Polynomial Arithmetic
Author:
- Wayne EberlyWEWayne Eberly
- 1 October 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (5) , 955-976
Abstract
Parallel algorithms for polynomial arithmetic—multiplication of n polynomials of degree m, polynomial division with remainder, and polynomial interpolation—are presented. These algorithms can be implemented using polynomial time constructible families of Boolean circuits of polynomial size and optimal order depth, or log space constructible families of polynomial size and near optimal depth, for computations over $\mathbb{Z},\mathbb{Q}$, finite fields, and several other domains. Arithmetic circuits of polynomial size and optimal order depth are obtained for polynomial arithmetic over arbitrary fields.
Keywords
This publication has 19 references indexed in Scilit:
- The parallel complexity of exponentiating polynomials over finite fieldsJournal of the ACM, 1988
- Log Depth Circuits for Division and Related ProblemsSIAM Journal on Computing, 1986
- Fast parallel algorithms for polynomial division over an arbitrary field of constantsComputers & Mathematics with Applications, 1986
- Polynomial division and its computational complexityJournal of Complexity, 1986
- Fast parallel polynomial division via reduction to triangular toeplitz matrix inversion and to polynomial inversion modulo a powerInformation Processing Letters, 1985
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Parallel Solution of Certain Toeplitz Linear SystemsSIAM Journal on Computing, 1984
- Parallel computation for well-endowed rings and space-bounded probabilistic machinesInformation and Control, 1983
- Fast parallel matrix and GCD computationsInformation and Control, 1982