Multivariate division algorithm
Encyclopedia
In mathematics
, polynomial
s 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s in more than one variable do not form a Euclidean domain
Euclidean domain
In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...
, 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
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
on polynomials where h >h' iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
the largest monomial which is in exactly one of h and h' is in h. Therefore this process will eventually terminate.