A fast parallel sparse polynomial GCD algorithm
This work introduces a parallel modular GCD algorithm for sparse multivariate polynomials with integer coefficients. The computation of the GCD of multivariate polynomials is known as an important problem in symbolic computation and has been studied by many authors. The bottleneck in this problem was always the growth of the coefficients through the computations until modular algorithms appeared in the 70s, which are really efficient for sparse polynomials. In this work, the authors combine a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. Throughout the article, they explain in detail the strengths (fast, highly parallelizable) and weaknesses (existence of unlucky homomorphisms, that is, unlucky evaluation points) of their methodology. They also compare their implementation with the serial implementations they have done of Zippel's GCD algorithm in Maple and Magma.
- A method for solving key equation for decoding goppa codes
- Algorithms for the non-monic case of the sparse modular GCD algorithm
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- An improved EZ-GCD algorithm for multivariate polynomials
- An Improved Multivariate Polynomial Factoring Algorithm
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- Diversification improves interpolation
- Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm
- Early termination in sparse interpolation algorithms
- Factoring Polynomials Over Large Finite Fields
- Fast parallel multi-point evaluation of sparse polynomials
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation
- Handbook of finite fields
- scientific article; zbMATH DE number 3147675 (Why is no real title available?)
- scientific article; zbMATH DE number 3977110 (Why is no real title available?)
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 108109 (Why is no real title available?)
- scientific article; zbMATH DE number 1263395 (Why is no real title available?)
- scientific article; zbMATH DE number 2221909 (Why is no real title available?)
- Improved Division by Invariant Integers
- Interpolating polynomials from their values
- Interpolation of polynomials given by straight-line programs
- Modern computer algebra
- Modular algorithm for sparse multivariate polynomial interpolation and its parallel implementation
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
- On Euclid's Algorithm and the Theory of Subresultants
- On sparse interpolation over finite fields
- On the bit-complexity of sparse polynomial and series multiplication
- Randomized root finding over finite FFT-fields using tangent Graeffe transforms
- Shift-register synthesis and BCH decoding
- Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values
- Subresultants and Reduced Polynomial Remainder Sequences
- Symbolic-numeric sparse interpolation of multivariate polynomials
- The Berlekamp-Massey algorithm revisited
- The EEZ-GCD algorithm
- Three new algorithms for multivariate polynomial GCD
- Using sparse interpolation in Hensel lifting
- Computing sparse GCD of multivariate polynomials via polynomial interpolation
- An improved EZ-GCD algorithm for multivariate polynomials
- Modular algorithm for sparse multivariate polynomial interpolation and its parallel implementation
- Parallel polynomial operations on SMPs: An overview
- Parallel algorithms on greatest common divisor of polynomial system
- A fast parallel sparse polynomial GCD algorithm
- Irreducibility and greatest common divisor algorithms for sparse polynomials
- scientific article; zbMATH DE number 1263395 (Why is no real title available?)
- scientific article; zbMATH DE number 1273687 (Why is no real title available?)
- scientific article; zbMATH DE number 871951 (Why is no real title available?)
- Parallel sparse polynomial multiplication on modern hardware architectures
- Algorithms for the non-monic case of the sparse modular GCD algorithm
- Computing GCDs of Multivariate Polynomials over Algebraic Number Fields Presented with Multiple Extensions
- Approximate GCD of several multivariate sparse polynomials based on SLRA interpolation
- Bit complexity of polynomial GCD on sparse representation
- A new sparse polynomial GCD by separating terms
This page was built for publication: A fast parallel sparse polynomial GCD algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994882)
