Karim BELABAS on Thu, 9 Oct 2003 14:48:19 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polcompositum() vs factornf() performance comparison |
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]