Re: poldisc shortcut known but not used

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

* Phil Carmody [2008-04-16 11:15]:
> It appears that this is well known:
> 
>> There's more than one way to calculate a polynomial discriminant.
>> It  turns out that when the coefficients are ugly multivariate (but
>> exact)  expressions, one of the polresultant() algorithms is much
>> faster.   Says so right in the manual!  For a monic polynomial px of
>> degree m,  poldisc(px) and polresultant(px,deriv(px)) differ
>> formally by a factor  of (-1)^(m(m-1)/2).  Dragging out the old
>> chestnut polynomial shows  that the manual wasn't kidding about the
>> other algorithm being faster:
>>
>> ? px=x^10 + (2*B*u + (2*A + 4*B))*x^9 + (9*A*u + (9*A +
>> (9*B - 45)))*x^8 + ((-24*A - 120)*u + (-24*A + (-24*B - 120)))*x^7
>> + ((-42*B + 210)*u + (-42*A + (-84*B + 210)))*x^6 + 252*x^5 + (42*B*u
>> + (42*A + 84*B))*x^4 + (24*A*u + (24*A + (24*B - 120)))*x^3 + ((-9*A
>> - 45)*u + (-9*A + (-9*B - 45)))*x^2 + ((-2*B + 10)*u + (-2*A + (-4*B
>> + 10)))*x + 1;
>> ? disc1=poldisc(px);
>> time = 46,859 ms.
>> ? disc2=-polresultant(px,deriv(px),x,2);\\Factor of -1 is (-1)^(10*9/2)
>> time = 10,475 ms.

( You may use px' instead of deriv(px). )

> Is there any reason why this case can't be detected automatically, and
> the shortcut used internally?

Had never gotten around to understanding my own implementation
(never include algorithms you don't understand:-).

Did that yesterday.

In the svn repository, polresultant(), poldisc() [ and all functions
that call them, e.g. charpoly(t_POLMOD) ] now use a combination of
1) modular algorithms for univariate polynomials over Z/Q,
2) Ducos's subresultant for other exact polynomials (with major
improvements for "simple" polynomials).
3) and Sylvester's matrix when nothing else works

4) our previous subresultant has almost disappeared, but survives in
functions like gcd() / bezout() / bezoutres(), for the time being.
Not for long in the case of gcd(); the other two are more annoying and
I probably won't adapt 2) to this case.

Since 1) takes over the "simple base ring" case, and other "simple" cases
are now treated adequately by 2), the latter now becomes the default.
The threshold with 4) was easy to determine: after a few simple
improvements, "ugly multivariate" turned out to encompass all
multivariate polynomials, as well as the univariate ones of large degree...

polresultant(P,Q,,2) is kept for backward compatibility, but gives you
the default.

There's a new 'test-resultant' bench, exhibiting cases where the new
subresultant is clearly superior to the old one.

I'm interested in all regression cases :-).

Cheers,

    K.B.

P.S: Someday, someone may sit down and implement proper
evaluation/interpolation schemes for general multivariate polynomials,
but it's definitely not a priority... the case that matters to PARI is
Z[X,Y], and it is already treated adequately.

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