Very Fast Parallel Polynomial Arithmetic

DOI10.1137/0218066zbMATH Open0694.68029OpenAlexW2052788392MaRDI QIDQ3470109FDOQ3470109

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

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

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)

Cited In (38)

• The parallel complexity of exponentiating polynomials over finite fields
• Title not available (Why is that?)
• The enumerability of P collapses P to NC
• Title not available (Why is that?)
• Feasible arithmetic computations: Valiant's hypothesis
• Fast Parallel Computation of the Polynomial Remainder Sequence via Bézout and Hankel Matrices
• Threshold Circuits for Iterated Matrix Product and Powering
• Title not available (Why is that?)
• Faster polynomial multiplication via multipoint Kronecker substitution
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• BALANCED DENSE POLYNOMIAL MULTIPLICATION ON MULTI-CORES
• Title not available (Why is that?)
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
• 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
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• Inversion in finite fields using logarithmic depth
• Title not available (Why is that?)
• Interpolating Arithmetic Read-Once Formulas in Parallel
• On design of circuits of logarithmic depth for inversion in finite fields
• Finding a vector orthogonal to roughly half a collection of vectors
• Fast and parallel interval arithmetic
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• Title not available (Why is that?)
• Parallel identity testing for skew circuits with big powers and applications
• Massively parallel computations on many-variable polynomials
• Boolean circuits versus arithmetic circuits
• A logarithmic Boolean time algorithm for parallel polynomial division
• Title not available (Why is that?)
• Dense polynomial multiplication with reduced array manipulation overhead
• Computing Powers in Parallel
• Complexity of computation in finite fields
• Functional decomposition of polynomials: the tame case
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• Fast Multiplication for Skew Polynomials
• Title not available (Why is that?)

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)