column

A parallel algorithm to compute the greatest common divisor of sparse multivariate polynomials

Authors:

Jiaxiong Hu,

Michael MonaganAuthors Info & Claims

ACM Communications in Computer Algebra, Volume 47, Issue 3/4

Pages 108 - 109

https://doi.org/10.1145/2576802.2576817

Published: 28 January 2014 Publication History

Get Access

Abstract

No abstract available.

References

[1]

M. BEN-Or, P. Tiwari: A deterministic algorithm for sparse multivariate polynomial interpolate. Proc. 20th annual ACM Symp Theory Comp, 1988, 301--309.

Digital Library

Google Scholar

[2]

M. Giesbrecht, G. Labahn, W-S. Lee: Symbolic-numeric sparse interpolation of multivariate polynomials. ISSAC'06, 2006.

Digital Library

Google Scholar

[3]

E. Kaltofen, Y.N. Lakshman, J-M. Wiley: Modular rational sparse multivariate polynomial interpolation. Watanabe and Nagata, 1990, 135--139.

Digital Library

Google Scholar

[4]

P. Wang: The EEZ-GCD Algorithm. SIGSAM Bulletin, 14, 1980, 50--60.

Digital Library

Google Scholar

[5]

R. E. Zippel: Probabilistic algorithms for sparse polynomials. EUROSAM '79, Springer-Verlag LNCS, 2, 1979, 216--226.

Digital Library

Google Scholar

Cited By

View all

Law MMonagan MPernet C(2015)A parallel implementation for polynomial multiplication modulo a primeProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790291(78-86)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790291
Gibson MMonagan MPernet C(2015)Optimizing and parallelizing the modular GCD algorithmProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790287(44-52)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790287

Recommendations

Using an Efficient Sparse Minor Expansion Algorithm to Compute Polynomial Subresultants and the Greatest Common Denominator

In this paper, the use of an efficient sparse minor expansion method to directly compute the subresultants needed for the greatest common denominator (GCD) of two polynomials is described. The sparse minor expansion method (applied either to Sylvester's ...
Computing the Greatest Common Divisor of Polynomials Using the Comrade Matrix
Computer Mathematics
Abstract
The comrade matrix of a polynomial is an analogue of the companion matrix when the matrix is expressed in terms of a general basis such that the basis is a set of orthogonal polynomials satisfying the three-term recurrence relation. We present the ...
Barnett's Theorems About the Greatest Common Divisor of Several Univariate Polynomials Through Bezout-like Matrices

This article provides a new presentation of Barnett s theorems giving the degree (resp. coefficients) of the greatest common divisor of several univariate polynomials with coefficients in an integral domain by means of the rank (resp. linear ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Communications in Computer Algebra

ACM Communications in Computer Algebra Volume 47, Issue 3/4

September/December 2013

116 pages

ISSN:1932-2232

EISSN:1932-2240

DOI:10.1145/2576802

Editors:
Manuel Kauers
RISC, J. Kepler University of Linz, Austria
,
Massimo Caboara
Università di Genova, Italy
,
Jean-Guillaume Dumas
Université Joseph Fourier, Grenoble, France
,
Laureano Gonzalez-Vega
Universidad de Cantabria, Santander, Spain
,
Eugene Zima
Wilfrid Laurier University, Waterloo ON, Canada
,
Michael Wester
Cotopaxi, Albuquerque NM, USA
,
Lihong Zhi
Academia Sinica, Beijing, China

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 January 2014

Published in SIGSAM-CCA Volume 47, Issue 3/4

Check for updates

Qualifiers

Column

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
56
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Law MMonagan MPernet C(2015)A parallel implementation for polynomial multiplication modulo a primeProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790291(78-86)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790291
Gibson MMonagan MPernet C(2015)Optimizing and parallelizing the modular GCD algorithmProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790287(44-52)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790287

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Using an Efficient Sparse Minor Expansion Algorithm to Compute Polynomial Subresultants and the Greatest Common Denominator

Computing the Greatest Common Divisor of Polynomials Using the Comrade Matrix

Barnett's Theorems About the Greatest Common Divisor of Several Univariate Polynomials Through Bezout-like Matrices