Re: polcoeff() mystery

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

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/