Re: gcd

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* macsyma [2019-08-08 03:20]:
> The greatest common divisor of P and Q defined in
> http://macsyma.starfree.jp/temp/PQ.gp
> is a polynomial with degree 35.(these are in composite form f(x^35))
> 
> But It seems that PARI's gcd(P,Q) does not return the result.

In current master (after commit 3abd162c), it requires about 12 minutes.

The reason we run into trouble is that we use a naive algorithm
[Euclidean remainder sequence (ERS), no modular computation] *but*, since the
base field is too complicated for PARI to identify it (anything involving
mutivariate polynomials), we use a naive subresultant which strives to
maintain "integrality" by multiplying by leading coefficients raised to huge
powers (in this case: due to your sparse polynomials and large degree
differences). And we waste an enormous amount of time inverting gigantic
leading coeficients when performing what the algorithm expects to be an
"exact" scalar division.

In this case, this is much worse than a direct ERS (either generic or
normalizing each remainder so that it becomes monic before being used in the
next Euclidean division). In other cases, the subresultant will be superior.

  ? R=gcd(P,Q); liftpol(R/pollead(R))
  time = 12min, 11,853 ms.
  %3 = x^35 + ((-2814705810*c7^5 - 12865509020*c7^4 - 2956013550*c7^3 + 6832839580*c7^2 - 3002993630*c7 - 7609289760)*c5^3 + (-11072532380*c7^5 - 12027706250*c7^4 - 2118210780*c7^3 - 1424986990*c7^2 - 3002993630*c7 + 1673794090)*c5^2 + (-1236699170*c7^5 - 11980726170*c7^4 - 11980726170*c7^3 - 1236699170*c7^2 - 2932502040)*c5 + (-9449209994*c7^5 - 18890856012*c7^4 - 9081390038*c7^3 - 7779009056*c7^2 - 15991519880*c7 - 9462010960))

  ? install(RgX_gcd_simple,GG); \\ direct ERS
  ? R=RgX_gcd_simple(P,Q); liftpol(R/pollead(R))
  time = 1,329 ms.
  %5 = x^35 + ((-2814705810*c7^5 - 12865509020*c7^4 - 2956013550*c7^3 + 6832839580*c7^2 - 3002993630*c7 - 7609289760)*c5^3 + (-11072532380*c7^5 - 12027706250*c7^4 - 2118210780*c7^3 - 1424986990*c7^2 - 3002993630*c7 + 1673794090)*c5^2 + (-1236699170*c7^5 - 11980726170*c7^4 - 11980726170*c7^3 - 1236699170*c7^2 - 2932502040)*c5 + (-9449209994*c7^5 - 18890856012*c7^4 - 9081390038*c7^3 - 7779009056*c7^2 - 15991519880*c7 - 9462010960))

I'm interested in any *simple* choice criterion between the two naive
algorithms, and even more by reasonably generic benchmarks. Currently, we use
subresultant by default (for low degree polynomials I seems to be generically
superior; of course your example involves huge degrees...); direct ERS is used
only if the field of scalars is such that we can rule out coefficient
explosion, e.g., t_PADIC or t_INTMOD coefs, t_POLMOD with t_INTMOD coefs; but
not t_POLMOD with t_INT coefs ...

I'm interested in reasonably generic benchmarks to help fine tune the
criterion. When the base field is simple, e.g. a finite field or a number
field, we use dedicated efficient algorithms (multimodular + half-gcd); it's
only when the base field is "unknown" that we need a better heuristic
than the current one.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`