Re: polcompositum() vs factornf() performance comparison

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Wed, Oct 08, 2003 at 02:19:53PM -0400, Igor Schein wrote:
> Hi,
> 
> ? 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 ) is twice slower!!  

That is not surprising. factornf job is not finished when it has done
factoring the compositum. It needs to map factors over Z of
the compositum to factors of p2 over the field defined by p1, by taking gcd
of polynomials defined over a numberfield (nfgcd).

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.

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

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.

Cheers,
Bill.