Multivariate division algorithm

In mathematics, polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm; but an approximate multivariate division algorithm can be constructed.

Given a polynomial g, polynomials (f₁, ..., f_m) and an order on the monomials in k[x₁, ..., x_n], we construct the reduction of g modulo f₁, ..., f_m by the following algorithm. Let a_i denote the leading term of f_i with respect to the monomial order. Repeatedly apply the following until no monomial term of g is divisible by any of the a_i :

Take the smallest i such that the a_i divides some term of g. Let h be the largest (again with respect to the monomial ordering) term of g which is divisible by a_i, and replace g by g − (h / a_i )f_i.

Each time g changes in this procedure, it gets strictly smaller relative to the partial lexicographic order on polynomials where h >h' iff the largest monomial which is in exactly one of h and h' is in h. Therefore this process will eventually terminate.

Notes

• Rather distressingly, the final value of g can depend on the order in which the original f₁, ..., f_m are given. In fact, it is possible that the algorithm will yield 0 in some cases, but nonzero values in others. This problem disappears when working with a Gröbner basis.

• When n = 1 this procedure collapses down to the standard Euclidean algorithm for polynomials.