Multivariate division algorithm

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (September 2011)

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.