|Bill Allombert on Wed, 8 Oct 2003 22:43:32 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: polcompositum() vs factornf() performance comparison|
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.