Ilya Zakharevich on Fri, 5 May 2000 13:51:56 -0400

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

Re: Bug in Mod (2.0.15)

On Fri, May 05, 2000 at 10:39:47AM +0200, Bill Allombert wrote:
> >Do not see what you mean.  Which other places (in addition to
> >simplify()) depend-on/use the K(y,z,t)[X] hack?
> Well I want sometimes really to compute in K(y,z,t)[X] and I do not
> want this capability to be removed.

I would hate to remove the functionality.  So the question is how to
express your willingness to allow denomiators in y,z,t in terms of
PARI type system.  An obvious solution which comes to mind is to have
"unreduced fractions" with denominator 1 in the modulus as an
indication of this.

> Moreover there are lot of interesting ring beside K[X,Y,Z]. The good
> solution is to design a "ring" type to specify in which ring we do
> the computation.  At least : Z[X,Y], Q[X,Y] and Q(Y)[X]

"Type" system is wished very much indeed.  A possible solution would
be to have a new primitive type typed-vector, which is same as vector
calculation-wise, but the last component is a string with the type.

> >Given marked generators (x,y,z etc) of the ring, could not we get
> >something canonical?
> I check it in a book:
> No, but does it really matter ?

Yes and Yes.  Why it is possible:

Completely order monomials so that

  M1 * M2 <= M1
  M1 < M2	<=>	M1 * M < M2 * M.

Semi-order polynomials by comparing highest monomials.  Then each
class x + I in A/I has a unique minimal representative (up to
normalization).  Similarly, there is a unique minimal element in I \ {0},
say, P1, there is unique element in I/(P1 * A) with minimal possible
representative etc.

This gives a canonical basis (at least for polynomials over a field,
but probably over some rings too), and I thought it is the same
procedure as for Groebner bases.

> We only need to be able to: 
> _ check wether an element is in an ideal or not.
> _ Reduce an element modulo an ideal to avoid coefficient explosion.
> _ Compute inverse if it exists.
> and Groebner basis can handle this.

We also need to able to compare things for equality.

> >Why this obsession with efficiency?  It is good when possible, but
> >having *some* pilot implementation will clear the way for future
> >improvements...
> PARI does not handle sparse polynomials, and this is a big limitation,
> even for moderate input. Probably it is better to implement it before
> Groebner basis.

I still see these things (ability and efficiency) as orthogonal.