Multivariate division algorithm

From Wikipedia, the free encyclopedia

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 repeatedly applying the following procedure until doing so leaves g unchanged:

Let a_i denote the leading term of f_i with respect to our ordering. 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.

[edit] 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.