Multivariate division algorithm
|
|
Although polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm, 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 repeatedly applying the following procedure until doing so leaves g unchanged:
Let ai denote the leading term of fi with respect to our ordering. 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 Gröbner bases.
- When n = 1 this procedure collapses down to the standard Euclidean algorithm for polynomials.