|
|
|
|
|
Multivariate Division AlgorithmAlthough 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..., 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 Grbner bases.
*When n = 1 this procedure collapses down to the standard Euclidean algorithm for polynomials.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|