# Avoiding infinite loop in multi variable polynomial division

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?

• You need to use a monomial order. See Cox, Little, O'Shea's Ideals Varieties and Algorithms. – Michael Burr Oct 25 '15 at 12:56

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.
• This method calculates that $x^2/(x+y) = x^2/(x+y)$ but that $y^2/(x+y) = y-x + x^2/(x+y)$. So it seems somewhat imperfect and it's not clear which answer is better either! – Scott Oct 25 '15 at 14:34