Re: polcompositum() vs factornf() performance comparison

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

On Wed, 8 Oct 2003, Igor Schein wrote:
> ? p1= x^16+8*x^14+148*x^12-184*x^10+5680*x^8-102304*x^6+546088*x^4-1557232*x^2+4351396;
> ? p2=x^16+8*x^14-152*x^12+416*x^10+13030*x^8-12904*x^6+15688*x^4+954368*x^2+657721;
> ? #
>    timer = 1 (on)
> ? poldegree((p=polcompositum(p1,p2))[#p])
> time = 1,110 ms.
> 32
> ? matsize(factornf(p1,subst(p2,x,y)))
> time = 2,260 ms.
> [8, 2]
>
> 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 )

No. It depends on the input data. The interface is completely inappropriate
because I did not finish the implantation of my variant of van Hoeij's
algorithm in arbitrary orders. It should always call nfroots. Currently it
only does so when the 2nd argument is of nf type.

> is twice slower!!
> Any comment?

Yes. Both commands return much more information than your stated needs. The
first one is a bit less wasteful [ factoring over Z is easier than over
a number field of degree 16. Here you compute many extra gcds ].

  nfisisom(p1, nfinit(p2))

should be about 10 times faster. The nfinit call can be replaced by
nfinit([p2, nfbasis(p2, 1)]) if the discriminant of p2 is not smooth.

Also possible is

  nfroots( nfinit(subst(p2,x,y)), p1 )

which should be about as fast. If you don't need the isomorphism, you can
improve a little on the above, but it's not available from GP.

Cheers,

    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]