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 (f_{1}, ..., f_{m}) and an order on the monomials in k[x_{1}, ..., x_{n}], we construct the reduction of g modulo f_{1}, ..., 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_{1}, ..., 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.
Categories: Polynomials
 Computer algebra
Wikimedia Foundation. 2010.
Look at other dictionaries:
Multivariate — may refer to: in Mathematics Multivariable calculus Multivariate division algorithm Multivariate interpolation Multivariate polynomial in Statistics Multivariate analysis Multivariate random variable Multivariate statistics in other areas… … Wikipedia
Buchberger's algorithm — In computational algebraic geometry and computational commutative algebra, Buchberger s algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. It was… … Wikipedia
Kmeans algorithm — The k means algorithm is an algorithm to cluster n objects based on attributes into k partitions, k < n. It is similar to the expectation maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural… … Wikipedia
Gröbner basis — In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R. One can view it as a multivariate, non linear… … Wikipedia
List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… … Wikipedia
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia
Greatest common divisor of two polynomials — Informally, the greatest common divisor (GCD) of two polynomials p ( x ) and q ( x ) is the biggest polynomial that divides evenly into both p ( x ) and q ( x ). The definition is modeled on the concept of the greatest common divisor of two… … Wikipedia
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… … Wikipedia
kmeans clustering — In statistics and data mining, k means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean. This results into a partitioning of… … Wikipedia