Richard Fateman <fateman@cs.berkeley.edu> writes:
> Stavros Macrakis wrote:
> >Wolfgang Jenkner posted a patch to subres for the algebraic case,
> >but if I'm not mistaken, spmod still works better in general.
> It is actually pretty surprising the subres has bugs. It should be
> the simplest program.
It is not that SUBRES has further bugs but rather that it tends to
expose other problems.
Here's some trivial algebraic reasoning to explain how I think that
things work:
I think that binding $ALGEBRAIC to T means that we are working in some
algebra A = Z[U, V, ..., X]/I where U, V, ..., X are the various
"kernels" (in Maxima parlance) and I is the ideal generated by the
algebraic dependencies. Now what does it mean to calculate the gcd
(via subres) of two elements p and q in A? The subres gcd algorithm
really wants univariate polynomials over a unique factorisation
domain, so we have to pick some "kernel", say X, and regard it as an
indeterminate, somehow, that is, we have to get rid of algebraic
dependencies involving X. This last point is what the current version
of subres fails to do and what my patch tries to fix in the following
way: Assume that A is an integral domain (that is, I is prime) and let
K be its field of fractions. Take some new indeterminate (over K),
say T, and consider the K-algebra epimorphism
f: K[T] --> K where T |-> X
Given an element p of K we consider the p' in K[T] which is defined by
taking the "current" representation of p and replacing every
occurrence of X by T. In particular this implies f(p') = p.
Note that the implementation actually does not work by explicitly
introducing such a new T but by just not mentioning (the main
variable) X, which is the usual way many functions in the rational
functions module work.
Now, for p and q in A, the subres gcd(p', q') =: r' is well defined by
the algorithm itself and we can just define the subres gcd(p, q) :=
f(r').
Of course, r' is necessarily the same as the gcd calculated by any
other algorithm, except for some factor which is a unit of K[T], that
is, a non-zero element of K. In principle, this would allow for any
element in K to become the gcd of p and q, but, in fact, Maxima
normalises this factor somehow.
Now a typical problem looks like this: Maxima wants to simplify some
quotient p/q and calculates the subres gcd(p, q) as above. Suppose
that the subres gcd(p', q') = q' (so that q' divides p' in K[T]).
This implies that the subres gcd(p, q) = q, so Maxima expects p/q to
simplify to a polynomial. However at the point when this
simplification is actually performed (by functions like PQUOTIENT) the
appearance of p/q might have changed because of algebraic
dependencies. In particular, the denominator of this quotient might
have acquired a higher degree in the main variable than the numerator
(and hence messages like `Quotient by a polynomial of higher degree').
The way algebraic dependencies are used depends also on the ordering
on variables, so simply exchanging variables sometimes works. I'll
post an example for this in the `ode2 not providing the solution'
thread.
BTW, my patch and an example for the sort of things it is supposed to
fix was in
http://www.math.utexas.edu/pipermail/maxima/2003/003694.html
Wolfgang