Association for Computing Machinery (ACM)

A Fast Parallel Sparse Polynomial GCD Algorithm

Jiaxiong Hu ¹

Michael Monagan ¹

Hide authors affiliations Show authors affiliations: 1 affiliation

Simon Fraser University, Burnaby, BC, Canada |

Publication type: Proceedings Article

Publication date: 2016-07-20

Association for Computing Machinery (ACM)

DOI: 10.1145/2930889.2930903

Copy DOI

Abstract

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 Cilk C. We compare it with Maple and Magma's implementations of Zippel's GCD algorithm.

Found

Top-30

Journals

	1 2 3 4
Lecture Notes in Computer Science	Lecture Notes in Computer Science, 4, 23.53% Lecture Notes in Computer Science 4 publications, 23.53%
ACM Communications in Computer Algebra	ACM Communications in Computer Algebra, 2, 11.76% ACM Communications in Computer Algebra 2 publications, 11.76%
Computer Physics Communications	Computer Physics Communications, 2, 11.76% Computer Physics Communications 2 publications, 11.76%
Journal of Complexity	Journal of Complexity, 2, 11.76% Journal of Complexity 2 publications, 11.76%
Symmetry	Symmetry, 1, 5.88% Symmetry 1 publication, 5.88%
IEEE Transactions on Emerging Topics in Computing	IEEE Transactions on Emerging Topics in Computing, 1, 5.88% IEEE Transactions on Emerging Topics in Computing 1 publication, 5.88%
Concurrency Computation Practice and Experience	Concurrency Computation Practice and Experience, 1, 5.88% Concurrency Computation Practice and Experience 1 publication, 5.88%
Applicable Algebra in Engineering, Communications and Computing	Applicable Algebra in Engineering, Communications and Computing, 1, 5.88% Applicable Algebra in Engineering, Communications and Computing 1 publication, 5.88%
Mathematics of Computation	Mathematics of Computation, 1, 5.88% Mathematics of Computation 1 publication, 5.88%
Springer Proceedings in Mathematics and Statistics	Springer Proceedings in Mathematics and Statistics, 1, 5.88% Springer Proceedings in Mathematics and Statistics 1 publication, 5.88%
	1 2 3 4

Publishers

	1 2 3 4 5 6
Springer Nature	Springer Nature, 6, 35.29% Springer Nature 6 publications, 35.29%
Elsevier	Elsevier, 4, 23.53% Elsevier 4 publications, 23.53%
Association for Computing Machinery (ACM)	Association for Computing Machinery (ACM), 3, 17.65% Association for Computing Machinery (ACM) 3 publications, 17.65%
MDPI	MDPI, 1, 5.88% MDPI 1 publication, 5.88%
Institute of Electrical and Electronics Engineers (IEEE)	Institute of Electrical and Electronics Engineers (IEEE), 1, 5.88% Institute of Electrical and Electronics Engineers (IEEE) 1 publication, 5.88%
Wiley	Wiley, 1, 5.88% Wiley 1 publication, 5.88%
American Mathematical Society	American Mathematical Society, 1, 5.88% American Mathematical Society 1 publication, 5.88%
	1 2 3 4 5 6

We do not take into account publications without a DOI.
Statistics recalculated weekly.

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.

Metrics

Publisher

Association for Computing Machinery (ACM)