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.

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

  • K-means 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

  • k-means 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.