MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Q--PolynomialReduce



Ersek_Ted%PAX1A@mr.nawcad.navy.mil wrote:
> 
> Hello,
> This is Ted Ersek
> 
> I was going over a solution Daniel Lichtblau posted to the Mathgroup a
> few  weeks ago.
> The lines below are very similar to the solution he gave.
> 
> A user may want to let (t=x*u+y*v) and express ( (x*u+y*v)u+(-x*u-y*v)v
> )  in terms of (t).  This would give (t*u-t*v).
> 
> Daniel pointed out that the last part of what comes from
> PolynomialReduce  gives the desired result (when given the right
> arguments).
> 
> Any of the lines In[1] through In[5] below seem to work.  I was then
> wondering how the third argument of PolynomialReduce effects the
> results.
>  For In[6] I let the third argument be something unrelated to the
> problem,  and I got a very different result.  So it seems the third
> argument is used  in some way, but how?
> 
> I had a course in abstract algebra as an undergraduate.  In this course
> I  studied Groups, Rings, and Fields.  Also Daniel recently faxed me
> his  article on Grobner Bases in Mathematica 3.0.   This limited
> background may  help me understand PolynomialReduce, but I still have
> very little knowledge  of polynomial algebra.
> 
> In[1]:=
> PolynomialReduce[(x*u+y*v)u+(-x*u-y*v)v,{x*u+y*v-t},{x}]
> 
> Out[1]=
> {{u-v},t u-t v}
> 
> In[2]:=
> PolynomialReduce[(x*u+y*v)u+(-x*u-y*v)v,{x*u+y*v-t},{y}]
> 
> Out[2]=
> {{u-v},t u-t v}
> 
> In[3]:=
> PolynomialReduce[(x*u+y*v)u+(-x*u-y*v)v,{x*u+y*v-t},{u}]
> 
> Out[3]=
> {{u-v},t u-t v}
> 
> In[4]:=
> PolynomialReduce[(x*u+y*v)u+(-x*u-y*v)v,{x*u+y*v-t},{v}]
> 
> Out[4]=
> {{u-v},t u-t v}
> 
> In[5]:=
> PolynomialReduce[(x*u+y*v)u+(-x*u-y*v)v,{x*u+y*v-t},{x,y,u,v}]
> 
> Out[5]=
> {{u-v},t u-t v}
> 
> In[6]:=
> PolynomialReduce[(x*u+y*v)u+(-x*u-y*v)v,{x*u+y*v-t},{a}]
> 
> Out[6]=
> {{0}, u^2*x - u*v*x + u*v*y - v^2*y}

Think of PolynomialReduce as a term rewriter (which, in technical
jargon, is exactly what it is). Given an ordering on monomials it will
attempt to rewrite "larger" ones in terms of smaller ones. The default
ordering is lexicographic. We have some order on variables, and the
order on monomials is then "dictonary" order based thereon. For
example, if we order a>c>b, then the term t1=a^3*b^2*c^2 is greater
than t2=a^2*b^6*c^5 because it has larger exponent for the variable a.
It is smaller than t3=a^3*b*c^3 because they have the same exponent for
a, but t3 has larger exponent for c, which is next in the variable
ordering.

The third argument to PolynomialReduce provides an ordering on the set
of variables. Any variables in the input polynomials but not given here
will be made lexicographically smaller than those explicitly given. The
order thay have with respect to one another is unspecified and depends
on internal implementation details. In the examples with 

poly = (x*u+y*v)*u + (-x*u-y*v)*v;
redpoly = x*u + y*v - t;

if we give no variables, or, what amounts to the same thing, give a list
of variables that do not intersect with the ones actually used, then it
appears that t becomes the largest variable, hence nothing will be
rewritten in terms of t.

In[18]:= Last[PolynomialReduce[poly, redpoly]]
          2                      2
Out[18]= u  x - u v x + u v y - v  y

In[19]:= Last[PolynomialReduce[poly, redpoly, {t}]]
          2                      2
Out[19]= u  x - u v x + u v y - v  y

If we specify, say, {y} as our list of variables, then y becomes
lexicographically largest and wherever possible we rewrite terms
containing it in terms of smaller stuff.

In[20]:= Last[PolynomialReduce[poly, redpoly, {u}]] Out[20]= t u - t v


Daniel Lichtblau
Wolfram Research



  • Prev by Date: some trivia about Geometry`Polytopes`
  • Next by Date: How to get the solution area of inequation?
  • Prev by thread: Q--PolynomialReduce
  • Next by thread: LinearProgramming question (speed problem)