Ilya Zakharevich on Tue, 16 Jul 2002 08:23:12 -0400

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

Re: polcoeff() mystery

On Tue, Jul 16, 2002 at 01:47:37AM +0200, Karim BELABAS wrote:
> > Do you mean here the support for base arithmetic, or higher-level
> > stuff?  If former, it is not out-of-hand to fix...
> The following assumption occurs in _many_ places in the code: if x, y are
> t_POL in variable v, then so is f(x, y), for all low-level routines f,
> like gadd / gmul / gres, etc.  [ f(x,y) may be of degree 0, or -oo of course ]

Well, *this* particular assumption is very easy to live with.  (At
worst, it is a multiplicative factor of 2 for the "size" of objects.)
I thought more about assumptions like: if pol[3] is in variable 3,
then pol[4] is a poly too, and in the same variable.  I see that later
you say that this is not assumed...

> I was unclear in my previous messages. Most polynomial are not "filled"
> in the sense implied in your query. x^2 + y*x + z (input as is) is really
>   x^2 * 1 + x^1 * (1*y^1 + 0*y^0) + x^0 * y^0 * z
> This is not necessary: if input is x^2 + simplify(y*x) + z, one gets
>   x^2 * 1 + x^1 * (1*y^1 + 0*y^0) + x^0 * z
> which is also a correct object.
> 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.

> 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?

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).

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?