An improved EZ-GCD algorithm for multivariate polynomials (Q2518611)

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.