- 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 (f1, ..., fm) and an order on the monomials in k[x1, ..., xn], we construct the reduction of g modulo f1, ..., fm by the following algorithm. Let ai denote the leading term of fi with respect to the monomial order. Repeatedly apply the following until no monomial term of g is divisible by any of the ai :
Take the smallest i such that the ai divides some term of g. Let h be the largest (again with respect to the monomial ordering) term of g which is divisible by ai, and replace g by g − (h / ai )fi.
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 f1, ..., fm 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.
Categories:- Polynomials
- Computer algebra
Wikimedia Foundation. 2010.