Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: sorting polynomials by the degree of certain terms

• To: mathgroup at smc.vnet.net
• Subject: [mg49220] Re: [mg49202] sorting polynomials by the degree of certain terms
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Thu, 8 Jul 2004 02:50:54 -0400 (EDT)
• References: <200407070542.BAA25018@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

On 7 Jul 2004, at 14:42, David Hessing wrote:

>
> Hi,
>
> I dealing with huge polynomials (around 50,000 terms). Each term may
> contain some real coefficient, followed by any combination of 11
> variables, each of which may be raised to some some power. However,
> I'm interested in sorting the polynomial according to the sum of the
> degrees of only 2 of the variables. In other words, in the sorted
> expression, the first terms would be those where the two variables do
> not appear (the sum of their powers is zero). The next terms would be
> the terms where one of the two variables appeared raised to the power
> 1. The next terms would be the terms where both variables appeared
> with power 1, or just one of the variables appeared with power 2. And
> so on.
>
> I've played with passing the expression to the Sort function, along
> with a defined sorting function, but I can't get it to work. Any help
> would be greatly appreciated.
>
> -David
>

Presumably what you have in mind is ordering monomials?

You could define a monomial order function with respect to variables 
vars as follows:

MyOrderQ[f_, g_, vars_] := With[{
     a = Plus @@ Take[Exponent[f, vars], 2],
         b = Plus @@ Take[
           Exponent[g, vars], 2]}, Which[a < b, True, a == b, 
OrderedQ[{f,
         g}], True, False]]

What this does is compares the sums of the exponents of the first two 
variables in two monomials. The one with the  smaller sum is taken to 
be smaller. If the sums are equal then the canonical ordering is used.

So, with three variables x,y,z:


MyOrderQ[z^5,x y z,{x,y,z}]


True

This is because the sum of the exponents of x and y in z^5 is 0.


MyOrderQ[x,y,{x,y,z}]

True

and

MyOrderQ[y,x,{x,y,z}]

False

in this case the sums are the same so the canonical ordering is used (x 
comes before y)

And here is how you sort several monomials:


Sort[{x*y, x^2*y^2*z, x^4*z, z^3},
   MyOrderQ[#1, #2, {x, y, z}] & ]


{z^3, x*y, x^4*z, x^2*y^2*z}

Here there was again a "tie" for the last place when sums of powers 
were compared so the canonical ordering was used with x^4 coming before 
x^2 y^2. Of course one could easily reverse this.

(I hope I have not misunderstood you!)

Also, note that you can't just "sort" a polynomial, in the sense of  
arranging the order of its terms in your own order because Matheamtica 
will rearrange it into canonical order again. So what you need to do is 
to first convert it to a list and then sort. For example, to sort the 
polynomial

f = x*y + x^4*z + x^2*y^2*z + z^3;

you have to do something like:


Sort[List @@ f, MyOrderQ[#1, #2, {x, y, z}] & ]


{z^3, x*y, x^4*z, x^2*y^2*z}

But if you now apply Plus, Mathematica will at one re-arrange it in 
canonical order:

Plus @@ %

x*y + x^4*z + x^2*y^2*z + z^3

Andrzej Kozlowski
Chiba, Japan
http://www.mimuw.edu.pl/~akoz/

• References:
  • sorting polynomials by the degree of certain terms
    • From: hessing@gmail.com (David Hessing)