Luis Felipe Tabera Alonso on Fri, 16 Jul 2010 01:19:56 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: nffactor vs factornf |
On Friday July 16 2010, Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> wrote: > * Luis Felipe Tabera Alonso [2010-07-15 21:25]: > > According to the documentation, factornf uses Trager's trick to perform a > > factorization over the rationals and nffactor uses Van Hoeij's method, > > which is preferable in many cases, but it needs a nf structure. > > > > I have some complicated number fields where I would like to factor > > polynomials. If I already have the nf structure, I can use nffactor > > without problems. But for these fields nf is very expensive, so factornf > > is faster (I will not factor so many polynomials to do the effort). > > > > But, as I understand Van Hoeij method, one does not need the nf > > structure, it may increase performance though. I am correct? Is there a > > way to use Van Hoeij's method without computing nf of the number field? > > In the 'testing' branch, nffactor can live with a polynomial, instead of > an nf structure, and compute internally the parts of the (missing) nf > struct that it really needs : > > \\ trivial example > (00:08) gp > nf=nfinit(y^20-2); nffactor(nf,x^10-2); > time = 156 ms. > (00:08) gp > nffactor(y^20-2, x^10-2); \\ about as fast > time = 156 ms. > > \\ non-trivial example > (00:08) gp > p= x^20 - 64857820*x^19 - 3862862*x^18 - 150*x^16 - 30*x^14 - > 822*x^13 - 98578*x^11 + 8*x^9 + 43582*x^8 + 45*x^7 - 3033*x^6 - > 1958664*x^4 + 493666*x^3 - 44*x + 1 (00:08) gp > nffactor(subst(p,x,y),p); > time = 51,047 ms. > (00:09) gp > nf=nfinit(subst(p,x,y)); nffactor(nf, p); > time = 25,569 ms. > > N.B: nfinit(p) was very lucky in this case : it tries to factor a > general 200-digits integer, and succeeds "quickly" (because the latter is > almost prime...) > > > > What version are you using ? > > Cheers, > > K.B. Thanks for the fast answer! I am using the testing branch 2.4.2.alpha, I will try this, looks very good. I can live with a performance penalty of not having the full nfinit since the beginning. Luis > -- > Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 > Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 > 351, cours de la Liberation http://www.math.u-bordeaux.fr/~belabas/ > F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP] > `