Regular chain

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, and more specifically in computer algebra and elimination theory, a regular chain is a particular kind of triangular set of multivariate polynomials over a field, where a triangular set is a finite sequence of polynomials such that each one contains at least one more indeterminate than the preceding one. The condition that a triangular set must satisfy to be a regular chain is that, for every , every common zero (in an algebraically closed field) of the first polynomials may be prolongated to a common zero of the th polynomial. In other words, regular chains allow solving systems of polynomial equations by solving successive univariate equations without considering different cases. Regular chains enhance the notion of Wu's characteristic sets in the sense that they provide a better result with a similar method of computation.

In mathematics, and more specifically in computer algebra and elimination theory, a regular chain is a particular kind of triangular set of multivariate polynomials over a field, where a triangular set is a finite sequence of polynomials such that each one contains at least one more indeterminate than the preceding one. The condition that a triangular set must satisfy to be a regular chain is that, for every , every common zero (in an algebraically closed field) of the first polynomials may be prolongated to a common zero of the th polynomial. In other words, regular chains allow solving systems of polynomial equations by solving successive univariate equations without considering different cases. Regular chains enhance the notion of Wu's characteristic sets in the sense that they provide a better result with a similar method of computation. 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 and , respectively. Note that: (1) the content of the second polynomial is x 2 , which does not contribute to the generic points represented and thus can be removed; (2) the dimension of each component is 1, the number of free variables in the regular chain. R = k[x_1, \ldots, x_n] are always sorted as . A non-constant polynomial f in R can be seen as a univariate polynomial in its greatest variable. 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 with respect to u and a_e is the leading coefficient of f with respect to u. Then the initial of f is a_e and e is its main degree. Triangular set A non-empty subset T of R 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 , ..., t s } be a triangular set such that , h_i be the initial of t i and h be the product of h i 's. Then T is a regular chain if \mathrm{resultant}(h, T) = \mathrm{resultant}(\cdots(\mathrm{resultant}(h, t_s),\ldots, t_i)\cdots) \neq 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 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)} = \bigcap_{i=1}^e \sqrt{\mathrm{sat}(T_i)} . The second is to describe all zeroes in the Lazard sense, V(F) = \bigcup_{i=1}^e W(T_i) . There are various algorithms available for triangular decompositions in either sense. \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, p\in\mathrm{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)\neq0 and Hence the regularity test for sat(T) is algorithmic. Given a prime ideal P, there exists a regular chain C such that P = sat(C). If the first element of a regular chain C is an irreducible polynomial and the others are linear in their main variable, then sat(C) is a prime ideal. Conversely, if P is a prime ideal, then, after almost all linear changes of variables, there exists a regular chain C of the preceding shape 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. E. Hubert. [ftp://nozdr.ru/biblio/kolxo3/Cs/CsCa/Winkler%20F.,%20Langer%20U.%20(eds.)%20Symbolic%20and%20Numerical%20Scientific%20Computation%20(Proc.%20SNSC%202001,%20Hagenberg)(LNCS2630,%20Springer,%202003)(ISBN%203540405542)(398s)_CsCa_.pdf#page=51 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). 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 Intelligence in Mathematics, pp. 14715, Oxford University Press.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375767727 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.