An improved EZ-GCD algorithm for multivariate polynomials

DOI10.1016/J.JSC.2008.04.006MaRDI QIDQ2518611zbMATH OpenOpenAlexFDO

Authors Kuniaki Tsuji

Publication date 16 January 2009

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2008.04.006

zbMATH Keywords

Bad-zero problemEz-GCD

Mathematics Subject Classification ID

Computational aspects and applications of commutative rings (13P99)

Review text

The aim of this paper is improving the EZ-GCD (and EEZ-GCD) algorithm for sparse multivariate polynomials, in order to avoid the ``bad-zero problem [\textit{J. Moses} and \textit{D. Y. Y. Yun}, in: The EZ GCD algorithm, Proceedings of ACM National Conference, 159--166 (1973); \textit{P. S. Wang}, SIGSAM Bull. 14, No. 2, 50--60 (1980; Zbl 0445.68026); \textit{K. O. Geddes, S. R. Czapor} and \textit{G. Labahn}, Algorithms for computer algebra, (Dordrecht): Kluwer Academic Publishers Group. (1992; Zbl 0805.68072)]. The author introduces the use of the ``power ideal and power ideal with a prime number \(p\) (for short PI and PPI resp.) and from these the PI algorithm and PPI algorithm. In the first part of these algorithms, there is a ``specialization of the polynomials through a PI or a PPI; in this way the computations can be performed using the generalized Euclidean algorithm for a UFD and then the obtained result is lifted using Hensel's Lemma modulo a power ideal. With this technique, the intermediate expression growth of terms is reduced. The author also provides a study of the complexity of the new algorithms and some examples, enlightening both the cases in which the new algorithms are powerful and the cases in which EZ-GCD and EEZ-GCD still have better performances, making hypothesis about the reasons for these different behaviours.

Recommendations

• Improvement of EZ-GCD algorithm based on extended hensel construction
• Computing sparse GCD of multivariate polynomials via polynomial interpolation
• A fast parallel sparse polynomial GCD algorithm
• Improvements of the power-series coefficient polynomial remainder sequence GCD algorithm
• A fast parallel sparse polynomial GCD algorithm
• Computing approximate GCD of multivariate polynomials
• Three new algorithms for multivariate polynomial GCD
• The approximate GCD of inexact polynomials
• scientific article; zbMATH DE number 871950
• scientific article; zbMATH DE number 30376

Cites work

• An Improved Multivariate Polynomial Factoring Algorithm
• 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 1263398 (Why is no real title available?)
• scientific article; zbMATH DE number 481965 (Why is no real title available?)
• scientific article; zbMATH DE number 2151236 (Why is no real title available?)
• On Euclid's Algorithm and the Theory of Subresultants
• Polynomial Remainder Sequences and Determinants
• Subresultants and Reduced Polynomial Remainder Sequences
• The EEZ-GCD algorithm
• Three new algorithms for multivariate polynomial GCD

Cited in

(6)

• Three new algorithms for multivariate polynomial GCD
• A fast parallel sparse polynomial GCD algorithm
• On the extended Hensel construction and its application to the computation of real limit points
• An Efficient Algorithm for Computing Parametric Multivariate Polynomial GCD
• Improvement of EZ-GCD algorithm based on extended hensel construction
• A new sparse polynomial GCD by separating terms

This page was built for publication: An improved EZ-GCD algorithm for multivariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2518611)