Triangular decomposition

Last updated February 13, 2024

In computer algebra, a triangular decomposition of a polynomial system $S$ is a set of simpler polynomial systems $S 1, ..., S e$ such that a point is a solution of $S$ if and only if it is a solution of one of the systems $S 1, ..., S e$ .

When the purpose is to describe the solution set of $S$ in the algebraic closure of its coefficient field, those simpler systems are regular chains. If the coefficients of the polynomial systems $S 1, ..., S e$ are real numbers, then the real solutions of $S$ can be obtained by a triangular decomposition into regular semi-algebraic systems. In both cases, each of these simpler systems has a triangular shape and remarkable properties, which justifies the terminology.

History

The Characteristic Set Method is the first factorization-free algorithm, which was proposed for decomposing an algebraic variety into equidimensional components. Moreover, the Author, Wen-Tsun Wu, realized an implementation of this method and reported experimental data in his 1987 pioneer article titled "A zero structure theorem for polynomial equations solving".^[1] To put this work into context, let us recall what was the common idea of an algebraic set decomposition at the time this article was written.

Let $K$ be an algebraically closed field and $k$ be a subfield of $K$ . A subset $V \subset K n$ is an (affine) algebraic variety over $k$ if there exists a polynomial set $F \subset k [x 1, ..., x n]$ such that the zero set $V (F) \subset K n$ of $F$ equals $V$ .

Recall that $V$ is said irreducible if for all algebraic varieties $V 1, V 2 \subset K n$ the relation $V = V 1 \cup V 2$ implies either $V = V 1$ or $V = V 2$ . A first algebraic variety decomposition result is the famous Lasker–Noether theorem which implies the following.

Theorem (Lasker - Noether). For each algebraic variety

V \subset K n

there exist finitely many irreducible algebraic varieties

V 1, ..., V e \subset K n

such that we have

V=V_{1}\cup \cdots \cup V_{e}.

Moreover, if

V i ⊈ V j

holds for

1 \leq i < j \leq e

then the set

{V 1, ..., V e}

is unique and forms the irreducible decomposition of

V

.

The varieties $V 1, ..., V e$ in the above Theorem are called the irreducible components of $V$ and can be regarded as a natural output for a decomposition algorithm, or, in other words, for an algorithm solving a system of equations in $k [x 1, ..., x n]$ .

In order to lead to a computer program, this algorithm specification should prescribe how irreducible components are represented. Such an encoding is introduced by Joseph Ritt ^[2] through the following result.

Theorem (Ritt). If

V \subset K n

is a non-empty and irreducible variety then one can compute a reduced triangular set

C

contained in the ideal

\langle F\rangle

generated by

F

in

k [x 1, ..., x n]

and such that all polynomials

g

in

\langle F\rangle

reduces to zero by pseudo-division w.r.t

C

.

We call the set $C$ in Ritt's Theorem a Ritt characteristic set of the ideal $\langle F\rangle$ . Please refer to regular chain for the notion of a triangular set.

Joseph Ritt described a method for solving polynomial systems based on polynomial factorization over field extensions and computation of characteristic sets of prime ideals.

Deriving a practical implementation of this method, however, was and remains a difficult problem. In the 1980s, when the Characteristic set Method was introduced, polynomial factorization was an active research area and certain fundamental questions on this subject were solved recently^[3]

Nowadays, decomposing an algebraic variety into irreducible components is not essential to process most application problems, since weaker notions of decompositions, less costly to compute, are sufficient.

The Characteristic Set Method relies on the following variant of Ritt's Theorem.

Theorem (Wen-Tsun Wu). For any finite polynomial set

F \subset k [x 1, ..., x n]

, one can compute a reduced triangular set

C\subset \langle F\rangle

such that all polynomial

g

in

F

reduces to zero by pseudo-division w.r.t

C

.

Different concepts and algorithms extended the work of Wen-Tsun Wu. In the early 1990s, the notion of a regular chain, introduced independently by Michael Kalkbrener in 1991 in his PhD Thesis and, by Lu Yang and Jingzhong Zhang^[4] led to important algorithmic discoveries.

In Kalkbrener's vision,^[5] regular chains are used to represent the generic zeros of the irreducible components of an algebraic variety. In the original work of Yang and Zhang, they are used to decide whether a hypersurface intersects a quasi-variety (given by a regular chain). Regular chains have, in fact, several interesting properties and are the key notion in many algorithms for decomposing systems of algebraic or differential equations.

Regular chains have been investigated in many papers.^[6]^[7]^[8]

The abundant literature on the subject can be explained by the many equivalent definitions of a regular chain. Actually, the original formulation of Kalkbrener is quite different from that of Yang and Zhang. A bridge between these two notions, the point of view of Kalkbrener and that of Yang and Zhang, appears in Dongming Wang's paper.^[9]

There are various algorithms available for obtaining triangular decomposition of $V (F)$ both in the sense of Kalkbrener and in the sense of Lazard and Wen-Tsun Wu. The Lextriangular Algorithm by Daniel Lazard ^[10] and the Triade Algorithm by Marc Moreno Maza ^[11] together with the Characteristic Set Method are available in various computer algebra systems, including Axiom and Maple.

Formal definitions

Let $k$ be a field and $x 1 < ... < x n$ be ordered variables. We denote by $R = k [x 1, ..., x n]$ the corresponding polynomial ring. For $F \subset R$ , regarded as a system of polynomial equations, there are two notions of a triangular decomposition over the algebraic closure of $k$ . The first one is to decompose lazily, by representing only the generic points of the algebraic set $V (F)$ in the so-called sense of Kalkbrener.

{\sqrt {(F)}}=\bigcap _{i=1}^{e}{\sqrt {\mathrm {sat} (T_{i})}}.

The second is to describe explicitly all the points of $V (F)$ in the so-called sense of in Lazard and Wen-Tsun Wu.

V(F)=\bigcup _{i=1}^{e}W(T_{i}).

In both cases $T 1, ..., T e$ are finitely many regular chains of $R$ and ${\sqrt {\mathrm {sat} (T_{i})}}$ denotes the radical of the saturated ideal of $T i$ while $W (T i)$ denotes the quasi-component of $T i$ . Please refer to regular chain for definitions of these notions.

Assume from now on that $k$ is a real closed field. Consider $S$ a semi-algebraic system with polynomials in $R$ . There exist^[12] finitely many regular semi-algebraic systems $S 1, ..., S e$ such that we have

Z_{\mathbf {k} }(S)=Z_{\mathbf {k} }(S_{1})\cup \cdots \cup Z_{\mathbf {k} }(S_{e})

where $Z k (S)$ denotes the points of $k n$ which solve $S$ . The regular semi-algebraic systems $S 1, ..., S e$ form a triangular decomposition of the semi-algebraic system $S$ .

Examples

Denote $Q$ the rational number field. In $Q[x,y,z]$ with variable ordering $x>y>z$ , consider the following polynomial system:

S={\begin{cases}x^{2}+y+z=1\\x+y^{2}+z=1\\x+y+z^{2}=1\end{cases}}

According to the Maple code:

with(RegularChains):R:=PolynomialRing([x,y,z]):sys:={x^2+y+z-1,x+y^2+z-1,x+y+z^2-1}:l:=Triangularize(sys,R):map(Equations,l,R);

One possible triangular decompositions of the solution set of $S$ with using RegularChains library is:

{\begin{cases}z=0\\y=1\\x=0\end{cases}}\cup {\begin{cases}z=0\\y=0\\x=1\end{cases}}\cup {\begin{cases}z=1\\y=0\\x=0\end{cases}}\cup {\begin{cases}z^{2}+2z-1=0\\y=z\\x=z\end{cases}}

Related Research Articles

In mathematics, a field $F$ is algebraically closed if every non-constant polynomial in $F [x]$ has a root in $F$ .

Algebraic geometry is a branch of mathematics which uses abstract algebraic techniques, mainly from commutative algebra, to solve geometrical problems. Classically, it studies zeros of multivariate polynomials; the modern approach generalizes this in a few different aspects.

In commutative algebra, the Krull dimension of a commutative ring R, named after Wolfgang Krull, is the supremum of the lengths of all chains of prime ideals. The Krull dimension need not be finite even for a Noetherian ring. More generally the Krull dimension can be defined for modules over possibly non-commutative rings as the deviation of the poset of submodules.

In mathematics, a unique factorization domain (UFD) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is an integral domain in which every non-zero non-unit element can be written as a product of irreducible elements, uniquely up to order and units.

In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not specific to commutative rings. This distinction results from the high number of fundamental properties of commutative rings that do not extend to noncommutative rings.

In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial $x 2 - 2$ is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as $if it is considered as a polynomial with real coefficients. One says that the polynomial x 2 - 2 is irreducible over the integers but not over the reals.$

In algebraic geometry and commutative algebra, the Zariski topology is a topology that is primarily defined by its closed sets. It is very different from topologies that are commonly used in real or complex analysis; in particular, it is not Hausdorff. This topology was introduced primarily by Oscar Zariski and later generalized for making the set of prime ideals of a commutative ring a topological space.

Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Modern definitions generalize this concept in several different ways, while attempting to preserve the geometric intuition behind the original definition.

In mathematics, an affine algebraic plane curve is the zero set of a polynomial in two variables. A projective algebraic plane curve is the zero set in a projective plane of a homogeneous polynomial in three variables. An affine algebraic plane curve can be completed in a projective algebraic plane curve by homogenizing its defining polynomial. Conversely, a projective algebraic plane curve of homogeneous equation $h (x, y, t) = 0$ can be restricted to the affine algebraic plane curve of equation $h (x, y, 1) = 0$ . These two operations are each inverse to the other; therefore, the phrase algebraic plane curve is often used without specifying explicitly whether it is the affine or the projective case that is considered.

In algebraic geometry, an affine algebraic set is the set of the common zeros over an algebraically closed field $k$ of some family of polynomials in the polynomial ring $An affine variety or affine algebraic variety, is an affine algebraic set such that the ideal generated by the defining polynomials is prime.$

In mathematics, a scheme is a mathematical structure that enlarges the notion of algebraic variety in several ways, such as taking account of multiplicities and allowing "varieties" defined over any commutative ring.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, an algebraic function field (often abbreviated as function field) of n variables over a field k is a finitely generated field extension K/k which has transcendence degree n over k. Equivalently, an algebraic function field of n variables over k may be defined as a finite field extension of the field K = k(x₁,...,x_n) of rational functions in n variables over k.

In mathematics, the Lasker–Noether theorem states that every Noetherian ring is a Lasker ring, which means that every ideal can be decomposed as an intersection, called primary decomposition, of finitely many primary ideals. The theorem was first proven by Emanuel Lasker for the special case of polynomial rings and convergent power series rings, and was proven in its full generality by Emmy Noether.

In mathematics, differential algebra is, broadly speaking, the area of mathematics consisting in the study of differential equations and differential operators as algebraic objects in view of deriving properties of differential equations and operators without computing the solutions, similarly as polynomial algebras are used for the study of algebraic varieties, which are solution sets of systems of polynomial equations. Weyl algebras and Lie algebras may be considered as belonging to differential algebra.

In number theory, Hilbert's irreducibility theorem, conceived by David Hilbert in 1892, states that every finite set of irreducible polynomials in a finite number of variables and having rational number coefficients admit a common specialization of a proper subset of the variables to rational numbers such that all the polynomials remain irreducible. This theorem is a prominent theorem in number theory.

Wenjun Wu's method is an algorithm for solving multivariate polynomial equations introduced in the late 1970s by the Chinese mathematician Wen-Tsun Wu. This method is based on the mathematical concept of characteristic set introduced in the late 1940s by J.F. Ritt. It is fully independent of the Gröbner basis method, introduced by Bruno Buchberger (1965), even if Gröbner bases may be used to compute characteristic sets.

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 $k$ , every common zero (in an algebraically closed field) of the $k$ first polynomials may be prolongated to a common zero of the $(k + 1)$ th polynomial. In other words, regular chains allow solving systems of polynomial equations by solving successive univariate equations without considering different cases.

A system of polynomial equations is a set of simultaneous equations $f 1 = 0, ..., f h = 0$ where the $f i$ are polynomials in several variables, say $x 1, ..., x n$ , over some field $k$ .

In mathematics, a positive polynomial (respectively non-negative polynomial) on a particular set is a polynomial whose values are positive (respectively non-negative) on that set. Precisely, Let p be a polynomial in n variables with real coefficients and let S be a subset of the n-dimensional Euclidean space ℝⁿ. We say that:

References

↑ Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2–12
↑ Ritt, J. (1966). Differential Algebra. New York, Dover Publications
↑ A. M. Steel Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic
↑ 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.
↑ M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143–167 (1993)
↑ S.C. Chou and X.S. Gao. On the dimension of an arbitrary ascending chain. Chinese Bull. of Sci., 38:799--804, 1991.
↑ Michael Kalkbrener. Algorithmic properties of polynomial rings. J. Symb. Comput.}, 26(5):525--581, 1998.
↑ P. Aubry, D. Lazard, M. Moreno Maza. On the theories of triangular sets. Journal of Symbolic Computation, 28(1–2):105–124, 1999.
↑ D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221–236
↑ D. Lazard, Solving zero-dimensional algebraic systems. Journal of Symbolic Computation 13, 1992
↑ M. Moreno Maza: On triangular decomposition of algebraic varieties. MEGA 2000 (2000).
↑ Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. Triangular decomposition of semi-algebraic systems. Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187--194, 2010.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2–12

[2] Ritt, J. (1966). Differential Algebra. New York, Dover Publications

[3] A. M. Steel Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic

[4] 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.

[5] M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143–167 (1993)

[6] S.C. Chou and X.S. Gao. On the dimension of an arbitrary ascending chain. Chinese Bull. of Sci., 38:799--804, 1991.

[7] Michael Kalkbrener. Algorithmic properties of polynomial rings. J. Symb. Comput.}, 26(5):525--581, 1998.

[8] P. Aubry, D. Lazard, M. Moreno Maza. On the theories of triangular sets. Journal of Symbolic Computation, 28(1–2):105–124, 1999.

[9] D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221–236

[10] D. Lazard, Solving zero-dimensional algebraic systems. Journal of Symbolic Computation 13, 1992

[11] M. Moreno Maza: On triangular decomposition of algebraic varieties. MEGA 2000 (2000).

[12] Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. Triangular decomposition of semi-algebraic systems. Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187--194, 2010.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]