Triangular decomposition

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".Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2–12 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 {{math|K}} be an algebraically closed field and {{math|k}} be a subfield of {{math|K}}. A subset {{math|V ⊂ Kⁿ}} is an (affine) algebraic variety over {{math|k}} if there exists a polynomial set {{math|F ⊂ k[x₁, ..., x_n]}} such that the zero set {{math|V(F) ⊂ Kⁿ}} of {{mvar|F}} equals {{mvar|V}}.

Recall that {{mvar|V}} is said irreducible if for all algebraic varieties {{math|V₁, V₂ ⊂ Kⁿ}} the relation {{math|V {{=}} V₁ ∪ V₂}} implies either {{math|V {{=}} V₁}} or {{math|V {{=}} V₂}}. A first algebraic variety decomposition result is the famous Lasker–Noether theorem which implies the following.

:Theorem (Lasker - Noether). For each algebraic variety {{math|V ⊂ Kⁿ}} there exist finitely many irreducible algebraic varieties {{math|V₁, ..., V_e ⊂ Kⁿ}} such that we have

::$V\; =\; V\_1\; \backslash cup\; \backslash cdots\; \backslash cup\; V\_e.$

:Moreover, if {{math|V_i ⊈ V_j}} holds for {{math|1 ≤ i < j ≤ e}} then the set {{math|{V₁, ..., V_e} }}is unique and forms the irreducible decomposition of {{mvar|V}}.

The varieties {{math|V₁, ..., V_e}} in the above Theorem are called the irreducible components of {{mvar|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 {{math|k[x₁, ..., 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 RittRitt, J. (1966). Differential Algebra. New York, Dover Publications through the following result.

:Theorem (Ritt). If {{math|V ⊂ Kⁿ}} is a non-empty and irreducible variety then one can compute a reduced triangular set {{mvar|C}} contained in the ideal $\backslash langle\; F\; \backslash rangle$ generated by {{mvar|F}} in {{math|k[x₁, ..., x_n]}} and such that all polynomials {{mvar|g}} in $\backslash langle\; F\; \backslash rangle$ reduces to zero by pseudo-division w.r.t {{mvar|C}}.

We call the set {{mvar|C}} in Ritt's Theorem a Ritt characteristic set of the ideal $\backslash langle\; F\; \backslash 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 recentlyA. M. Steel Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic

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 {{math|F ⊂ k[x₁, ..., x_n]}}, one can compute a reduced triangular set $C\; \backslash subset\; \backslash langle\; F\; \backslash rangle$ such that all polynomial {{mvar|g}} in {{mvar|F}} reduces to zero by pseudo-division w.r.t {{mvar|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 ZhangYang, L., Zhang, J. (1994). [http://www.iaea.org/inis/collection/NCLCollectionStore/_Public/22/086/22086436.pdf Searching dependency between algebraic equations: an algorithm applied to automated reasoning]. Artificial Intelligence in Mathematics, pp. 14715, Oxford University Press. led to important algorithmic discoveries.

In Kalkbrener's vision,M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143–167 (1993) 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.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. [http://www.sciencedirect.com/science/article/pii/S0747717199902699 On the theories of triangular sets]. Journal of Symbolic Computation, 28(1–2):105–124, 1999.

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.D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221–236

There are various algorithms available for obtaining triangular decomposition of {{math|V(F)}} both in the sense of Kalkbrener and in the sense of Lazard and Wen-Tsun Wu. The Lextriangular Algorithm by Daniel LazardD. Lazard, Solving zero-dimensional algebraic systems. Journal of Symbolic Computation 13, 1992 and the Triade Algorithm by [http://www.csd.uwo.ca/~moreno/ Marc Moreno Maza]M. Moreno Maza: On triangular decomposition of algebraic varieties. MEGA 2000 (2000). together with the Characteristic Set Method are available in various computer algebra systems, including Axiom and Maple.

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

: $\backslash sqrt\{(F)\}=\backslash bigcap\_\{i=1\}^\{e\}\backslash sqrt\{\backslash mathrm\{sat\}(T\_i)\}.$

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

: $V(F)=\backslash bigcup\_\{i=1\}^\{e\}W(T\_i).$

In both cases {{math|T₁, ..., T_e}} are finitely many regular chains of {{mvar|R}} and $\backslash sqrt\{\backslash mathrm\{sat\}(T\_i)\}$ denotes the radical of the saturated ideal of {{math|T_i}} while {{math|W(T_i)}} denotes the quasi-component of {{math|T_i}}. Please refer to regular chain for definitions of these notions.

Assume from now on that {{math|k}} is a real closed field. Consider {{mvar|S}} a semi-algebraic system with polynomials in {{mvar|R}}. There existChangbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. [http://www.sciencedirect.com/science/article/pii/S0747717111002070/pdf?md5=9344a2f6467b91cc32bcef52f9275ab2&pid=1-s2.0-S0747717111002070-main.pdf&_valck=1 Triangular decomposition of semi-algebraic systems]. Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187--194, 2010. finitely many regular semi-algebraic systems {{math|S₁, ..., S_e}} such that we have

:$Z\_\{\backslash mathbf\{k\}\}(S)\; =\; Z\_\{\backslash mathbf\{k\}\}(S\_1)\; \backslash cup\; \backslash cdots\; \backslash cup\; Z\_\{\backslash mathbf\{k\}\}(S\_e)$

where {{math|Z_k(S)}} denotes the points of {{math|kⁿ}} which solve {{mvar|S}}. The regular semi-algebraic systems {{math|S₁, ..., S_e}} form a triangular decomposition of the semi-algebraic system {{mvar|S}}.

Denote {{mvar|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 {{mvar|S}} with using [http://www.regularchains.org/ RegularChains] library is:

:$\backslash begin\{cases\}\; z\; =\; 0\; \backslash \backslash \; y\; =\; 1\; \backslash \backslash \; x\; =\; 0\; \backslash 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}

• Wu's method of characteristic set
• Regular chain
• Regular semi-algebraic system

{{Reflist}}

Category:Equations

Category:Algebra

Category:Polynomials

Category:Algebraic geometry

Category:Computer algebra

Category:Computer algebra systems