A fast parallel sparse polynomial GCD algorithm
type: Item
instance of: scholarly article
title: A fast parallel sparse polynomial GCD algorithm
zbMATH Open document ID: 1477.68549
author: Jiaxiong Hu
author: Michael Monagan
published in: Journal of Symbolic Computation
publication date: 2021-02-18T00:00:00Z
review text: 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.
reviewed by: Gema Maria Diaz Toca
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 13P05
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 7312663
zbMATH Keywords: modular algorithms
zbMATH Keywords: sparse polynomial interpolation
zbMATH Keywords: multivariate polynomial GCD computation
describes a project that uses: tangent Graeffe
describes a project that uses: Maple
describes a project that uses: GCDHEU
MaRDI profile type: Publication
full work available at URL: j.jsc.2020.06.001
OpenAlex ID: W3036931303
cites work: The Berlekamp-Massey algorithm revisited
cites work: Factoring Polynomials Over Large Finite Fields
cites work: On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
cites work: On Euclid's Algorithm and the Theory of Subresultants
cites work: GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation
cites work: Subresultants and Reduced Polynomial Remainder Sequences
cites work: Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values
cites work: Interpolation of polynomials given by straight-line programs
cites work: Modern computer algebra
cites work: Q4023676
cites work: Q3263792
cites work: Symbolic-numeric sparse interpolation of multivariate polynomials
cites work: Diversification improves interpolation
cites work: Randomized root finding over finite FFT-fields using tangent Graeffe transforms
cites work: On the bit-complexity of sparse polynomial and series multiplication
cites work: On sparse interpolation over finite fields
cites work: Q3743382
cites work: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
cites work: Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm
cites work: Early termination in sparse interpolation algorithms
cites work: Algorithms for the non-monic case of the sparse modular GCD algorithm
cites work: Shift-register synthesis and BCH decoding
cites work: Improved Division by Invariant Integers
cites work: Fast parallel multi-point evaluation of sparse polynomials
cites work: Using Sparse Interpolation in Hensel Lifting
cites work: Handbook of finite fields
cites work: Modular algorithm for sparse multivariate polynomial interpolation and its parallel implementation
cites work: An improved algorithm for computing logarithms over&lt;tex&gt;GF(p)&lt;/tex&gt;and its cryptographic significance (Corresp.)
cites work: Q4234286
cites work: Three new algorithms for multivariate polynomial GCD
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Q5702555
cites work: A method for solving key equation for decoding goppa codes
cites work: An improved EZ-GCD algorithm for multivariate polynomials
cites work: The EEZ-GCD algorithm
cites work: An Improved Multivariate Polynomial Factoring Algorithm
cites work: Q3851616
cites work: Interpolating polynomials from their values
DOI: 10.1016/J.JSC.2020.06.001
description: scientific article; zbMATH DE number 7312663