Regular chain

Regular chain

In computer algebra, a regular chain is a particular kind of triangular set in a multivariate polynomial ring over a field. It enhances the notion of characteristic set.

Introduction

Given a linear system, one can convert it to a triangular system via Gaussian elimination. For the non-linear case, given a polynomial system F over a field, one can convert (decompose or triangularize) it to a finite set of triangular sets, in the sense that the algebraic variety "V"(F) is described by these triangular sets. A triangular set may merely describe the empty set. To fix this degenerated case, the notion of regular chain was introduced, independently by Kalkbrener (1993), Yang and Zhang (1994). Regular chains also appear in Chou and Gao (1992). Regular chains are special triangular sets which are used in different algorithms for computing unmixed-dimensional decompositions of algebraic varieties. Without using factorization, these decompositions have better properties that the ones produced by Wu's algorithm. Kalkbrener's original definition was based on the following observation: every irreducible variety is uniquely determined by one of its generic points and varieties can be represented by describing the generic points of their irreducible components. These generic points are given by regular chains.

Examples

Denote Q the rational number field. In Q [x1, x2, x3] with variable ordering x1 < x2 < x3,: T = { x_2^2-x_1^2, x_2(x_3-x_1)}is a triangular set and also a regular chain. Two generic points given by "T" are (a, a, a) and (a, -a, a) where "a" is transcendental over Q.Thus there are two irreducible components, given by { x2 - x1, x3 - x1 } and { x2 + x1, x3 - x1 }, repectively.Note that: (1) the content of the second polynomial is x2, which does not contribute the generic points represented and thus can be reomved; (2) the dimension of each component is 1, the number of free variables in the regular chain.

Formal definitions

The variables in the polynomial ring mathrm{P}_n=k [x_1, ldots, x_n] are always sorted as x_1preccdotsprec x_n. A non-constant polynomial fin mathrm{P}_n can be seen as a univariate polynomial in its greatest variable.

*Notions

The greatest variable in "f" is called its main variable, denoted by mvar(f). Let "u" be the main variable of "f" and write it as f=a_eu^e+cdots+a_0, where "e" is the degree of "f" w.r.t. "u" and a_e is the leading coefficient of "f" w.r.t. "u". Then the initial of "f" is a_e and "e" is its main degree.

*Triangular set

A non-empty subset "T" of mathrm{P}_n is a triangular set, if the polynomials in "T" are non-constant and have distinct main variables. Hence, a triangular set is finite, and has cardinality at most "n".

*Regular chain

Let T={t_1,ldots, t_s} be a triangular set such that mathrm{mvar}(t_1)preccdotsprecmathrm{mvar}(t_s), h_i be the initial of "t"i and "h" be the product of hi's. Then "T" is a regular chain if : mathrm{resultant}(h, T)=mathrm{resultant}(cdots(mathrm{resultant}(h, t_s),ldots, t_1)cdots) eq 0, where each resultant is computed with respect to the main variable of "t"i, respectively. This definition is from Yang and Zhang, which is of much algorithmic flavor.

*Quasi-component and saturated ideal of a regular chain

The quasi-component "W"("T") described by the regular chain "T" is :W(T)=V(T)setminus V(h), that is,the set difference of the varieties "V"("T") and "V"("h"). The attached algebraic object of a regular chain is its saturated ideal :mathrm{sat}(T)=(T):h^infty. A classic result is that the Zariski closure of "W"("T") equals the variety defined by sat("T"), that is,:overline{W(T)}=V(mathrm{sat}(T)),and its dimension is n - |T|, the difference of the number of variables and the number of polynomials in "T".

*Triangular decompositions

In general, there are two ways to decompose a polynomial system "F". The first one is to decompose lazily, that is, only to represent its generic points in the (Kalkbrener) sense,: sqrt{(F)}=cap_{i=1}^{e}sqrt{mathrm{sat}(T_i)}.The second is to describe all zeroes in the (Lazard) sense,: V(F)=cup_{i=1}^{e}W(T_i).There are various algorithms available for triangular decompositions in either sense.

Properties

Let "T" be a regular chain in the polynomial ring mathrm{P}_n.

* The saturated ideal sat("T") is an unmixed ideal with dimension n − |"T"|.

* A regular chain holds a strong elimination property in the sense that:: mathrm{sat}(T cap k [x_1, ldots , x_i] ) = mathrm{sat}(T) cap k [x_1,ldots , x_i] .

* A polynomial "p" is in sat("T") if and only if p is pseudo-reduced to zero by "T", that is,: pinmathrm{sat}(T)iff mathrm{prem}(p, T)=0.:Hence the membership test for sat("T") is algorithmic.

* A polynomial p is a zero-divisor modulo sat("T") if and only if mathrm{prem}(p, T) eq0 and mathrm{resultant}(p, T)=0.:Hence the reguarity test for sat("T") is algorithmic.

* Given a prime ideal "P", there exists a regular chain "C" such that "P" = sat("C").

* A triangular set is a regular chain if and only if it is a Ritt characteristic set of its saturated ideal.

See also

*Characteristic set
*Groebner basis

Further references

* P. Aubry, D. Lazard, M. Moreno Maza. On the theories of triangular sets. Journal of Symbolic Computation, 28(1-2):105-124, 1999.
* F. Boulier and F. Lemaire and M. Moreno Maza. Well known theorems on triangular systems and the D5 principle. Transgressive Computing 2006, Granada, Spain.
* E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems. LNCS, volume 2630, Springer-Verlag Heidelberg.
* F. Lemaire and M. Moreno Maza and Y. Xie. The RegularChains library. Maple Conference 2005.
* M. Kalkbrener: Algorithmic Properties of Polynomial Rings. J. Symb. Comput. 26(5): 525-581 (1998).
* M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143-167 (1993).
* D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221-236.
* Yang, L., Zhang, J. (1994). Searching dependency between algebraic equations: an algorithm applied to automated reasoning. Artificial Intel ligence in Mathematics, pp. 147­15, Oxford University Press.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • chain store — one of a group of retail stores under the same ownership and selling similar merchandise. [1905 10, Amer.] * * * ▪ retailing operation       any of two or more retail stores having the same ownership and selling the same lines of goods. Chain… …   Universalium

  • Chain Code Pictures — Ketten Kode Bilder (Chain Code Pictures) sind Bilder, die in erster Linie mit Hilfe von formalen Grammatiken erzeugt werden. Die von solchen Grammatiken generierten Wörter werden hierbei jeweils als genau ein Bild interpretiert, indem die… …   Deutsch Wikipedia

  • Chain Hill — Coordinates: 51°34′58″N 1°25′8″W / 51.58278°N 1.41889°W / …   Wikipedia

  • chain gang — noun a gang of convicts chained together • Hypernyms: ↑gang, ↑crew, ↑work party * * * noun 1. : a gang of convicts chained together especially as an outside working party 2. slang : one of two or more railroad train crews ta …   Useful english dictionary

  • Polymerase chain reaction — PCR redirects here. For other uses, see PCR (disambiguation). A strip of eight PCR tubes, each containing a 100 μl reaction mixture The polymerase chain reaction (PCR) is a scientific technique in molecular biology to amplify a single or a… …   Wikipedia

  • Door chain — A door chain, security chain, or security door chain consists of a small chain attached to the door frame, which attaches to a track on the door for security purposes. It is a type of lock that is often used along with other types of locks to… …   Wikipedia

  • Medium chain triglycerides — (MCTs) are medium chain (6 to 12 carbons) fatty acid esters of glycerol. MCTs passively diffuse from the GI tract to the portal system (longer fatty acids are absorbed into the lymphatic system) without requirement for modification like long… …   Wikipedia

  • Mace and Chain — is the youngest landed secret society at Yale University. The society was founded in 1956 (four years after Manuscript), became inactive in the 1960s, and was revived in the 1990s. In 2001, it acquired a regular meeting place (called a tomb a 180 …   Wikipedia

  • Watch chain — Watch Watch (w[o^]ch), n. [OE. wacche, AS. w[ae]cce, fr. wacian to wake; akin to D. wacht, waak, G. wacht, wache. [root]134. See {Wake}, v. i. ] [1913 Webster] 1. The act of watching; forbearance of sleep; vigil; wakeful, vigilant, or constantly… …   The Collaborative International Dictionary of English

  • tactics — /tak tiks/, n. 1. (usually used with a sing. v.) the art or science of disposing military or naval forces for battle and maneuvering them in battle. 2. (used with a pl. v.) the maneuvers themselves. 3. (used with a sing. v.) any mode of procedure …   Universalium

Share the article and excerpts

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