Karim BELABAS on Wed, 17 Jul 2002 19:15:54 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polcoeff() mystery |
On Tue, 16 Jul 2002, Ilya Zakharevich wrote: > > What I meant is that most pari routines handle and produce univariate > > polynomials (for some irrelevant coefficient ring). > > "handle and produce"? I do not follow your intent here... I know a > lot of functions which may produce something else than polynomials. Right, I meant "most low-level arithmetic routines" (and most high level routines depend on this behaviour, so it's not trivial to change) > > So a given > > multivariate polynomial, depending on its "history" may contain lots of > > polynomials of degree 0, which are only removed by simplify() [which is > > hardly ever called in the library code]. > > And the result of simplify() may have a mixture of numbers and polys > as coefficients; and it is valid as input to other PARI functions... Right? Right. > This returns us back to the same question I'm asking again and again > (sorry for this!): time and time again I hear it on this list that the > reason why PARI is so bad with multivariate polynomials is the > wastefulness of the current representation. What I see (after > simplify()) is a *slightly wasteful* representation (in the worst case > the "storage size" per monomial is degree + #variables). This can be quite wasteful when you have monomials of relatively high degree But you are right: > Given that degree is usually very small, I do not see how such a > miniscule wastefulness may influence PARI. So is it wastefulness of > representation, or wastefulness of used algorithms which hinders > multivariate polynomials in PARI? OK, as I see it, the _real_ problem is Euclidean division / subresultant gcd. There's an incredible amount of gcd computations (to compute contents, when trying to symblify rational functions) for even relatively simple problems like: { M = [ a6, a5, a4, a3, a2, a1, 0, 0, 0, 0, 0, 0, 0, 0, 0; 0, 0, a6, 0, a5, a4, 0, a3, a2, a1, 0, 0, 0, 0, 0; 0, a6, 0, a5, a4, 0, a3, a2, a1, 0, 0, 0, 0, 0, 0; 0, 0, 0, a6, 0, 0, a5, a4, 0, 0, a3, a2, a1, 0, 0; 0, 0, 0, 0, a6, 0, 0, a5, a4, 0, 0, a3, a2, a1, 0; 0, 0, 0, 0, 0, a6, 0, 0, a5, a4, 0, 0, a3, a2, a1; 0, 0, 0, b6, 0, 0, b5, b4, 0, 0, b3, b2, b1, 0, 0; 0, 0, 0, 0, b6, 0, 0, b5, b4, 0, 0, b3, b2, b1, 0; 0, b6, 0, b5, b4, 0, b3, b2, b1, 0, 0, 0, 0, 0, 0; 0, 0, b6, 0, b5, b4, 0, b3, b2, b1, 0, 0, 0, 0, 0; 0, 0, 0, 0, 0, b6, 0, 0, b5, b4, 0, 0, b3, b2, b1; 0, 0, 0, 0, 0, c6, 0, 0, c5, c4, 0, 0, c3, c2, c1; 0, 0, c6, 0, c5, c4, 0, c3, c2, c1, 0, 0, 0, 0, 0; 0, c6, 0, c5, c4, 0, c3, c2, c1, 0, 0, 0, 0, 0, 0; 0, 0, 0, 0, c6, 0, 0, c5, c4, 0, 0, c3, c2, c1, 0 ]; } matdet(M) [ taken from a bench by Lewis & Wester, which tested a very inefficient alpha release of gp among other semi-CAS ] The modular bivariate resultants (over Z) I've implemented (for polcompositum, rnfequation & friends) beat the generic resultant routines by a few orders of magnitudes. I don't know what the "state-of-the-art" algorithm would be to handle this kind of problems (many variables, arbitrary coefficient ring). Recursive interpolation, possibly ? Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathematiques, Bat. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud Email: Karim.Belabas@math.u-psud.fr F-91405 Orsay (France) http://www.math.u-psud.fr/~belabas/ -- PARI/GP Home Page: http://www.parigp-home.de/