Karim BELABAS on Fri, 22 Jan 1999 13:11:25 +0100 (MET)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: poldisc

> > > p=a*x^3+b*x^2*y+c*x*y^2+d*y^3 + e*x^2+f*x*y+g*y^2 + h*x+i*y + h
> > > di=poldisc(p)
> > PARI's internal representation for polynomials... (highly non-symetrical,
> > optimized for 1 or 2 variables).
> > 
> > It is instantaneous with default stack, *IF* you make sure the
> > important variables have high priority:
> > gp> y; p=a*x^3+b*x^2*y+c*x*y^2+d*y^3 + e*x^2+f*x*y+g*y^2 + h*x+i*y + h
> >    ^^^ (now x and y are priviledged)
> What makes y important?  That p has slightly higher degree in y?

Yes; and more importantly so will the successive polynomials arising from the
pseudo-division remainder sequence. Division of multivariate polynomials are
a nightmare in PARI (the gcd computations will take forever); it gets
infinitely better if the polynomials are unitary (no divisions...) but that
will almost never be the case when computing resultants.

> Even if I assume that the polynomials are stored as sequences of
> coefficients wrt variables, and variables are (by default) ordered by
> the order PARI have seen them, 

They are.

> the difference between two orderings still seems to be a transposition of a
> matrix/tensor.  How may this affect speed?

In the sense that no effort is made to reorder the variables prior to the
computation. Try something like

f(n) = matdet(eval(matrix(n,n,i,j, Str("x" i "" j))))
f(6) \\ f(5) is still doable

under the debugger to see what I mean (see poldivres() getting crazy)

In fact, I am clueless as to what (moderately) efficient multivariate
division would require. Anybody able to help here ?

Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
PARI/GP Home Page: http://hasse.mathematik.-tu-muenchen.de/ntsw/pari/