Avoiding infinite loop in multi variable polynomial division

Question

I have written an algorithm that can successfully perform some algebraic long division but gets stuck on some problems with multiple variables in the denominator.

Here's an example expressed as you might do it by hand:

         x  -y  +y  -y
      -----------------------------
x + y | x^2                          -(x^2  + xy)
           -xy                       -(-xy - y^2)
                y^2                  -(xy + y^2)
                   -xy               -(-xy -y^2)
                       ... etc

The problem is (x^2 / (x + y)). At each iteration I'm choosing one of the terms in the numerator to divide by (quickly becomes y each time). But, because the denominator is made up of two parts with equal degrees, the algorithm just keeps recursing forever.

A more complicated example is:

         2y^2 - 2y^2
      -----------------------------------
x + y | 2xy^2 + x^2 + -2x^2y - 2xy - 3y^2
      -(2xy^2 + 2y^3)
      -----------------------------------
               -2y^3 + x^2 + -2x^2y - 2xy - 3y^2            
             -(-2y^3 -2xy^2)
             -----------------------------------
                     2xy^2 + x^2 + -2x^2y - 2xy - 3y^2
                     GOTO 10

This happens just when the denominator is made up of multiple terms with equal degree.

Is there a correct way to solve this bouncing back and forth?

Answer 1

The trick is to use a monomial order. A simple order is the lexicographic order where $x^ay^b>x^cy^d$ when $a>c$ or ($a=c$ and $b>d$). At every step of division, you check if the leading term of the divisor divides the leading term of the dividend. If so, proceed as above, if not, (for instance at the $y^2$ step) then the leading term becomes part of the remainder.