Evaluation of the Heuristic Polynomial GCDHsin-Chao (Phil) LiaoRichard J. Fateman*Computer Science Division, EECS DepartmentUniversity of California at BerkeleyAbstractThe Heuristic Polynomial GCD procedure (GCDHEU) isused by the Maple computer algebra system, but no other.Because Maple has an especially efficient kernel that pro-vides fast integer arithmetic, but a relatively slower inter-preter for non-kernel code, the GCDHEU routine is espe-cially effective in that it moves much of the computationinto “bignum” arithmetic and hence executes primarily inthe kernel.We speculated that in other computer algebra systems animplementation of GCDHEU would not be advantageous. Inparticular, if all the system code is compiled to run at ‘[fullspeed” in a (presumably more bulky) kernel that is entirelywritten in C or compiled Lisp, then there would seem to beno point in recasting the polynomial GCD problem into abignum GCD problem. Manipulating polynomials that arevectors of coefficients would seem to be equivalent compu-tationally to manipulating vectors of big digits.Yet our evidence suggests that one can take advantageof the GCDHEU in a Lisp system as well. Given a goodimplementation of bignums, for most small problems andmany large ones, a substantial speedup can be obtained bythe appropriate choice of GCD algorithm, including oftenenough, the GCDHEU approach. Another major winnerseem to be the subresultant polynomial remainder sequencealgorithm. Because more sophisticated sparse algorithmsare relatively slow on small problems and only occasionallyemerge as superior (on larger problems) it seems the choiceof a fast GCD algorithm is tricky.1 Introduction and objectivesIt is well known that GCD computations are very importantin computer algebra systems, especially in simplifying ratio-nal expressions, computing partial fraction expansions, andsimilar canonical transformations [5, 10]. It is also useful inconstructing reduced characteristic sets to prove geometrytheorems [2].*This work was supported in part by NSF Grant number CCR-9214963 and by NSF Infrastructure Grant number CDA-S72278S.Permission to copy without fee all or part of this material is grantedprovided that the copies are not made or distributed for direct com-mercial advantages, theACM copyright notice and the title of thepublication and its date appear, and notice is given that copying isby permission of the Association for Computing Machinery. To copyotherwise, or to republish, requires a fee and/or specific permission.ISSAC’95 - 7/95 Montreal, Canada@1995 ACM 0-89791-699-9/95/0007 $3.50Some GCD algorithms are based on some variation of theEuclidean algorithm extended to operate over a polynomialring. The most efficient known variant is the SubresultantPolynomial Remainder Sequence (PRS) algorithm [1, 3, 5,6].There are algorithms based on modular homomorphismsand their inverse mappings. Some algorithms require morethan one homomorphism in the construction of the GCD.One example is the modular algorithm based on Chineseremaindering (GCDCHREM) used in Maple [5]. The algo-rithms requiring only one homomorphic mapping are usu-ally based on the Hensel construction. Extended Zassen-haus GCD (EZGCD) and Extended EZGCD (EEZGCD)are of this type [8, 9]. Zippel’s Sparse Modular algorithm(SPMOD) incorporates evaluation homomorphism in finitefields, probabilistic sparse interpolation and univariate GCD[10].Rat her different in nature, the Heuristic GCD algorithm(GCDHEU) uses evaluation homomorphism over the inte-gers rather than finite fields [5]. It is not useful for largeproblems, and a carefully designed program will identify afailing case relatively rapidly, and move on to an alternativealgorithm.Of all the commercially available computer algebra sys-tems, only Maple uses GCDHEU. Maple has a small and effi-cient kernel that highly optimizes arithmetic of integers, andhas special code for univariate polynomials. More compli-cated computations such as multivariate polynomial GCDS)are programmed for execution by an efficient interpreterwhich is however much slower than kernel code. By mappingpolynomials into integers, GCDHEU executes primarily inthe kernel, simultaneously avoiding interpreter overhead inthis important algorithm, and still not taking up additionalkernel code space.GCDHEU is not implemented in any other system, prob-ably because their vendors assumed that in an environmentwhere all GCD procedures are compiled at full speed in C orLisp, there is no advantage in mapping polynomials (whichare vectors of coefficients) into bignums (which are vectorsof big digits). Rather than concentrating on implementa-tion tricks, the tendency has been to seek algorithmic ad-vantages (better asymptotic running times). The modularalgorithm, EZGCD and SPMOD replace bignum arithmeticwith allegedly faster modular single-word arithmetic. Theseminimize coefficient growth, where such growth is usuallya problem. GCDHEU, on the other hand, requires muchlarger evaluation points, thus almost inevitably forces cal-culations to continue into the bignum regime.Since thesize of evaluation point grows with the degree of the inputs,240GCDHEU is becomes less effective for large polynomials.Despite these drawbacks, our experiments suggest thatGCDHEU is useful, and the compiled/kernel versus inter-preter environment issue is not really a dominant factor. Itcan be used to good effect in a compiled Lisp environment.Our data show that, for low-degree polynomials in up to tenvariables, GCDHEU is faster than the Subresultant PRSmethod in the cases where the GCDS are non-monic anddense. It is faster than the EZGCD and SPMOD in severalcases, especially for polynomials with five or fewer variables.2 Review of GCD algorithmsIn this section, we briefly summarize each GCD algorithm,its advantages and disadvantages, and provide references.Subresultant PRS: The original PRS algorithm is theEuclidean algorithm using pseudo-division in a polynomialring. Its main problem is the large coefficient growth in-duced by pseudo-division. In the multivariate case, the co-efficients are themselves polynomials, and coefficient growthincludes an exponential growth in the degrees of the coeffi-cients. The Primitive PRS algorithm decreases such growthto a minimum by repeatedly removing the content of thepseudo-remainders at each iteration of the PRS. Becausethe contents are computed by GCDS, the Primitive PRSrequires many more operations than the Euclidean PRS.The