Re: polcompositum() vs factornf() performance comparison

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

On Wed, 8 Oct 2003, Bill Allombert wrote:
> On Wed, Oct 08, 2003 at 02:19:53PM -0400, Igor Schein wrote:
>> Basically, I am verifying in 2 different ways that 2 number fields are
>> non-isomorphic, but it turns out factornf ( for which nfisisom is a
>> wrapper ) is twice slower!!
[...]
> Karim and I have spent quite some time making the nfgcd routine fast,
> but it still often slower than the actual factorisation. This is what
> happens here.

That's because we spent even more time trying to make the polynomial
factorization routines fast over number fields [ over finite fields, it's
still slow ].

> I have two remarks: nfisisom use nfroots and not nffactor. Unfortunately
> there is no equivalent of nfroots for plain polynomial, so it uses
> factornf when the input are not given as nfinit() output. This make
> things much slower when the field are *not* isomorphic

This problem will disappear when nffactor / nfroots are able to work in
arbitrary orders. factornf() will not actually disappear since the method it
implements (Trager) is still optimal when factoring small polynomials over
fields of large degree, but it will in most cases default back to nffactor().

I need to find one or two hours to implement and debug this ( 99% of the code
is there ). Not likely in the weeks to come, though...

> Second, I see that factornf use indexpartial instead of plain
> discriminant. While it take 0 ms for most examples, this is wasteful
> since nfgcd() care only about `bad' primes dividing the denominator,
> not about the exponents which is what indexpartial reduce.

No. nfgcd calls matratlift(..., den), which calls lift_to_frac(..., den)
whose (heuristic) result must divide 'den'. Lowering den by reducing
exponents yields faster and more stringent tests.

I've benchmarked it, and it was (barely:-) faster.

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425   Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://www.parigp-home.de/  [PARI/GP]