Very Fast Parallel Polynomial Arithmetic

DOI10.1137/0218066MaRDI QIDQ3470109zbMATH OpenOpenAlexFDO

Authors Wayne Eberly

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218066

zbMATH Keywords

interpolationparallel algorithmscircuit depthpolynomial divisionpolynomial arithmetic\(NC^ 1\)-reductioniterated integer product

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Algorithms in computer science (68W99)

Recommendations

• On fast multiplication of polynomials over arbitrary algebras
• Computing Powers in Parallel
• scientific article; zbMATH DE number 18647
• Fast parallel algorithms for polynomial division over an arbitrary field of constants
• Parallel Algorithms for Algebraic Problems

Cited in

(38)

• scientific article; zbMATH DE number 1254017 (Why is no real title available?)
• Fast Multiplication for Skew Polynomials
• The parallel complexity of exponentiating polynomials over finite fields
• The enumerability of P collapses P to NC
• scientific article; zbMATH DE number 3958730 (Why is no real title available?)
• Feasible arithmetic computations: Valiant's hypothesis
• scientific article; zbMATH DE number 1263411 (Why is no real title available?)
• Fast Parallel Computation of the Polynomial Remainder Sequence via Bézout and Hankel Matrices
• Threshold Circuits for Iterated Matrix Product and Powering
• Faster polynomial multiplication via multipoint Kronecker substitution
• scientific article; zbMATH DE number 3856402 (Why is no real title available?)
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• BALANCED DENSE POLYNOMIAL MULTIPLICATION ON MULTI-CORES
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
• scientific article; zbMATH DE number 3999284 (Why is no real title available?)
• Matrix structures in parallel matrix computations
• Evaluation of circuits over nilpotent and polycyclic groups
• The iterated mod problem
• Algorithms for accurate, validated and fast polynomial evaluation
• Inversion in finite fields using logarithmic depth
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• scientific article; zbMATH DE number 18647 (Why is no real title available?)
• Interpolating Arithmetic Read-Once Formulas in Parallel
• On design of circuits of logarithmic depth for inversion in finite fields
• Fast and parallel interval arithmetic
• Finding a vector orthogonal to roughly half a collection of vectors
• scientific article; zbMATH DE number 4182832 (Why is no real title available?)
• Massively parallel computations on many-variable polynomials
• Parallel identity testing for skew circuits with big powers and applications
• Boolean circuits versus arithmetic circuits
• A logarithmic Boolean time algorithm for parallel polynomial division
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• Dense polynomial multiplication with reduced array manipulation overhead
• Parallel identity testing for skew circuits with big powers and applications
• Complexity of computation in finite fields
• Computing Powers in Parallel
• Functional decomposition of polynomials: the tame case
• Resolution of Hartmanis' conjecture for NL-hard sparse sets

This page was built for publication: Very Fast Parallel Polynomial Arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3470109)