0
$\begingroup$

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?

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

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ – Scott Oct 25 '15 at 14:34
  • 1
    $\begingroup$ It is imperfect (it depends on the choice of monomial order). If fact, unless you are dividing by a Groebner basis, then the remainder isn't even unique. I believe that it is provablly impossible to have a "best" answer according to your criterion! $\endgroup$ – Michael Burr Oct 25 '15 at 15:28
  • $\begingroup$ Excellent, that's what I wanted to hear. Thanks $\endgroup$ – Scott Oct 25 '15 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.