A fast parallel sparse polynomial GCD algorithm

Autor:	Michael Monagan, Jiaxiong Hu
Rok vydání:	2021
Předmět:	Mathematics::Number Theory Modulo MathematicsofComputing_NUMERICALANALYSIS 0102 computer and information sciences 010103 numerical & computational mathematics Cilk 01 natural sciences Magma (computer algebra system) Prime (order theory) Combinatorics symbols.namesake Integer Kronecker delta ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Computer Science::Symbolic Computation 0101 mathematics computer.programming_language Mathematics Discrete mathematics Binary GCD algorithm Algebra and Number Theory 010102 general mathematics Substitution (algebra) Lehmer's GCD algorithm Computational Mathematics Euclidean algorithm 010201 computation theory & mathematics symbols computer Integer (computer science)
Zdroj:	ISSAC
ISSN:	0747-7171
DOI:	10.1016/j.jsc.2020.06.001
Popis:	We present a parallel GCD algorithm for sparse multivariate polynomials with integer coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. We have implemented our algorithm in C for primes of various sizes and have parallelized it using Cilk C. We compare our implementation with Maple and Magma's serial implementations of Zippel's GCD algorithm.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1c4d363d1b0a36f05ac5f62f31ae0db3 https://doi.org/10.1016/j.jsc.2020.06.001 Zobrazit plný text záznamu Full Text from ScienceDirect