Keywords

1 Introduction

The method of triangular decomposition pioneered by Ritt [19] and Wu [23] has become a basic tool for computing the solutions of polynomial systems over an algebraically closed field. Given a finite set of polynomials F, this method decomposes F into finitely many systems of triangular shape such that the union of their zero sets is the same as that of F. With such decomposition in hand, many information on the solution set, such as emptiness, dimension, cardinality, etc., can be easily obtained. Triangular decomposition has been studied and gradually improved by many others in both theory [1, 2, 14, 15, 25] and algorithms [7, 10, 12, 13, 16, 17, 22, 24]. Efficient implementations exist in a Maple built-in package RegularChains as well as many other libraries and softwares, such as Epsilon, Wsolve, Magma, and so on.

Nowadays, triangular decomposition has also become an important back-end engine for several algorithms in studying semi-algebraic sets, such as real root classification [24] and comprehensive triangular decomposition of parametric semi-algebraic sets [5], computing sample points of semi-algebraic sets [4], describing semi-algebraic sets [4], as well as computing cylindrical algebraic decompositions and performing quantifier elimination [3, 8, 9]. These algorithms and their implementations make triangular decomposition become an efficient tool in many applications, such as theorem proving, program verification, stability analysis of biological systems, and so on.

To further improve the efficiency of triangular decomposition, one important direction is to explore the structure of input systems, such as symmetry and sparsity. The work of [11] brings the concept of variable sparsity to the world of triangular decomposition by virtue of the chordal graph of polynomial systems. Chordal graph already exists in many other contexts, such as Gauss elimination [20] and semidefinite optimization [21].

It has already been shown that some top-down algorithms [22] (up to minor modification of its original form) preserve chordality [18]. Incremental algorithms [7, 16, 17] are another important class, which compute triangular decompositions by induction on the number of polynomials. It is a natural question to ask if the incremental algorithms can also preserve chordality. In this paper, we provide an affirmative answer to this question for the incremental algorithm proposed in [6, 7]. On the other hand, we find that the current implementation of this algorithm in Triangularize command of the RegularChains library in Maple may not always respect chordality. After a careful examination of the implementation, we point out this is due to the use of some simplification operations. Finally, we show by experimentation that modifying these operations, together with some other optimizations, bring significant speedups for Triangularize on some super sparse polynomial systems.

2 Basic Lemmas

Definition 1

(Graph). Let \(\mathbf {x}=x_1,\ldots ,x_n\) and \(F\subset \mathbf {k}[\mathbf {x}]\). The (associated) graph \(\mathfrak {G}(F)\) of F is an undirected graph defined as follows:

  • The set V of vertices of \(\mathfrak {G}(F)\) is the set of variables appearing in F.

  • The set E of edges of \(\mathfrak {G}(F)\) is the set of \((x_i, x_j)\), \(i\ne j\), where \(x_i\) and \(x_j\) simultaneously appear in some \(f\in F\).

Denote by \(\mathfrak {v}(\mathfrak {G}(F))\) an operation which returns V.

Definition 2

(Perfect elimination ordering). Let \(\mathfrak {G}=(V, E)\) be a graph with vertices \(V=\{x_1,\ldots ,x_n\}\). An ordering \(\mathbf {x}=x_{i_1}>\cdots >x_{i_n}\) is a perfect elimination ordering for \(\mathfrak {G}\) if for any \(x_{i_j}\), the induced subgraph on the set of vertices \(V_{i_j}=\{x_{i_j}\}\cup \{x_{i_k}\mid x_{i_k}<x_{i_j}~\text{ and }~(x_{i_j},x_{i_k})\in E\}\) is a clique. If a perfect elimination ordering \(\mathbf {x}\) exists for \(\mathfrak {G}\), we say \(\mathfrak {G}\) is chordal (w.r.t. \(\mathbf {x}\)). We say that a graph \(\overline{\mathfrak {G}}\) with vertices \(V=\{x_1,\ldots ,x_n\}\) is a chordal completion of \(\mathfrak {G}\), if \(\overline{\mathfrak {G}}\) is chordal and \(\mathfrak {G}\) is a subgraph of \(\overline{\mathfrak {G}}\).

Example 1

Let \(F := \{x_1^2-x_2^2+x_2x_4, x_2^2-x_3x_4\}\). Then \(\mathfrak {G}(F)\) is illustrated in Fig. 1, where the vertex \(x_i\) is renamed as i for short. The ordering \(x_1>x_2>x_3>x_4\) is a perfect elimination ordering and \(\mathfrak {G}\) is chordal w.r.t. this ordering. Another ordering \(x_2>x_1>x_3>x_4\) is not a perfect elimination ordering.

Fig. 1.
figure 1

Chordal graph.

Full size image

Definition 3

Let \(\mathbf {x}\) be a given ordering and \(F\subset \mathbf {k}[\mathbf {x}]\). Let \(M:2^{\mathbf {k}[\mathbf {x}]}\rightarrow 2^{2^{\mathbf {k}[\mathbf {x}]}}\). Let \(\overline{\mathfrak {G}(F)}\) be any chordal completion of \(\mathfrak {G}(F)\) w.r.t. the ordering \(\mathbf {x}\) (that is \(\mathbf {x}\) is a perfect elimination ordering for \(\overline{\mathfrak {G}(F)}\)). We say that M preserves chordality in \(\mathfrak {G}(F)\) (resp. \(\overline{\mathfrak {G}(F)}\)) if for any \(S\in M(F)\), we have \(\mathfrak {G}(S)\subseteq \mathfrak {G}(F)\) (resp. \(\mathfrak {G}(S)\subseteq \overline{\mathfrak {G}(F)}\)). In the former case, we say that M strongly preserves chordality (for F). In the latter case, that is M preserves chordality in any chordal completion of \(\mathfrak {G}(F)\) w.r.t. \(\mathbf {x}\), we say that M preserves chordality (for F).

Remark 1

Let \(O:\mathbf {k}[\mathbf {x}]\rightarrow 2^{\mathbf {k}[\mathbf {x}]}\) be a unary operation which maps \(f\in \mathbf {k}[\mathbf {x}]\) to \(O(f)\subset \mathbf {k}[\mathbf {x}]\). Then it induces a map M which maps \(\{f\}\) to \(\{O(f)\}\). Let \(O:\mathbf {k}[\mathbf {x}]\times \mathbf {k}[\mathbf {x}]\rightarrow 2^{\mathbf {k}[\mathbf {x}]}\) be a binary operation which maps (f, g) to O(f, g). Then it induces a map M which maps \(\{f,g\}\) to \(\{O(f,g)\}\). For both cases, if M (strongly) preserves chordality, we say that the operation O (strongly) preserves chordality.

Example 2

Consider \(F := \{{x_{{1}}}^{3}-1,{x_{{2}}}^{3}-1,{x_{{3}}}^{3}-1,{x_{{4}}}^{3}-1,{x_{{1}}}^{2}+x_{{1}}x_{{2}}+{x_{{2}}}^{2},{x_{{2}}}^{2}+x_{{2}}x_{{3}}+{x_{{3}}}^{2},{x_{{3}}}^{2}+x_{{3}}x_{{4}}+{x_{{4}}}^{2},{x_{{1}}}^{2}+x_{{1}}x_{{4}}+{x_{{4}}}^{2}\}\). Figure 1 depicts a chordal completion \(\overline{\mathfrak {G}(F)}\) of \(\mathfrak {G}(F)\) w.r.t. the ordering \(x_1>x_2>x_3>x_4\). Let M be the Triangularize command in Maple 2019, which computes a set of regular chains as follows:

$$ \begin{array}{l} \{\{x_{{1}}+x_{{4}}+1,x_{{2}}-x_{{4}},x_{{3}}+x_{{4}}+1,{x_{{4}}}^{2}+x_{{4}}+1\},\\ \{x_{{1}}-1,x_{{2}}-x_{{4}},x_{{3}}+x_{{4}}+1,{x_{{4}}}^{2}+x_{{4}}+1\},\\ \{ \left( x_{{4}}-1 \right) x_{{1}}-x_{{4}}-2,x_{{2}}-1,x_{{3}}+x_{{4}}+1,{x_{{4}}}^{2}+x_{{4}}+1\},\\ \{x_{{1}}-1,{x_{{2}}}^{2}+x_{{2}}+1,x_{{3}}-1,{x_{{4}}}^{2}+x_{{4}}+1\},\\ \{x_{{1}}+x_{{4}}+1, \left( x_{{4}}+2 \right) x_{{2}}-x_{{4}}+1,x_{{3}}-1,{x_{{4}}}^{2}+x_{{4}}+1\},\\ \{\left( x_{{3}}+2 \right) x_{{1}}-x_{{3}}+1,x_{{2}}+x_{{3}}+1,{x_{{3}}}^{2}+x_{{3}}+1,x_{{4}}-1\},\\ \{{x_{{1}}}^{2}+x_{{1}}+1,x_{{2}}-1,{x_{{3}}}^{2}+x_{{3}}+1,x_{{4}}-1\}\}. \end{array} $$

As we see, it does not preserve chordality since the graph of the fifth regular chain is not a subgraph of \(\overline{\mathfrak {G}(F)}\).

Definition 4

Let \(O:K[\mathbf {x}]\rightarrow 2^{K[\mathbf {x}]}\) be a unary operation. We say that it respects the (elimination) ordering \(\mathbf {x}\) for \(f\in \mathbf {k}[\mathbf {x}]\) if \(\mathfrak {v}(O(f))\subseteq \mathfrak {v}(f)\).

Lemma 1

If a unary operation O respects the ordering, then it strongly preserves chordality.

Proof

It trivially holds since \(\mathfrak {G}(f)\) is a clique for any \(f\in \mathbf {k}[\mathbf {x}]\).

Definition 5

Given \(f\in \mathbf {k}[\mathbf {x}]\), let \(\text{ mvar }(f)\) be the largest variable appearing in f. Let \(O:\mathbf {k}[\mathbf {x}]\times \mathbf {k}[\mathbf {x}]\rightarrow 2^{\mathbf {k}[\mathbf {x}]}\) be a binary operation. Let \(S := O(f, g)\). We say that O respects the ordering \(\mathbf {x}\) (for f and g) if the following are satisfied:

  • If \(\text{ mvar }(f)=\text{ mvar }(g)\), we have \(\mathfrak {v}(S)\subseteq \mathfrak {v}(\{f, g\})\).

  • If \(\text{ mvar }(f)\ne \text{ mvar }(g)\), we have \(\mathfrak {v}(S)\subseteq \mathfrak {v}(f)\) or \(\mathfrak {v}(S)\subseteq \mathfrak {v}(g)\).

Lemma 2

Suppose that O respects the ordering \(\mathbf {x}\), then we have the following.

  • If \(\text{ mvar }(f)\ne \text{ mvar }(g)\), then O strongly preserves chordality.

  • If \(\text{ mvar }(f)=\text{ mvar }(g)\), then O preserves chordality.

Proof

Let \(\overline{\mathfrak {G}}\) be any chordal completion of \(\mathfrak {G}(\{f,g\})\) and \(x_i\) be the common main variable of f and g. By the definition of chordal graph, the subgraph of \(\overline{\mathfrak {G}}\) induced by the set of vertices \(\mathfrak {v}(\overline{\mathfrak {G}})\setminus \{x_i\}\) is a clique. So the conclusion holds.

Corollary 1

The irreducible factorization Factor strongly preserves chordality. If the two input polynomials have the same main variable, then the subresultant chain SubRes, the resultant res, the pseudo remainder prem and the pseudo quotient pquo operations w.r.t. the main variable preserve chordality.

If the input two polynomials do not have the same main variable, then these operations may destroy chordality, see Example 3.

Example 3

Consider the system \(F:=\{f_1,f_2\}\) again from Example 1 and the ordering \(x_1>x_2>x_3>x_4\). We have \(\text{ mvar }(f_1)=x_1\) and \(\text{ mvar }(f_2)=x_2\). Then \(\mathsf{prem}(f_1,f_2,x_2)={x_{{1}}}^{2}+x_{{2}}x_{{4}}-x_{{3}}x_{{4}}\). Clearly prem does not preserve chordality for \(f_1\) and \(f_2\).

Lemma 3

Let \(F\subset \mathbb {Q}[\mathbf {x}]\). Let p be a polynomial in F. Assume that F is chordal w.r.t. the variable order \(\mathbf {x}\). Let \(F' := F\setminus \{p\}\). Then there exists a chordal completion \(\overline{G(F')}\) of \(G(F')\) (with the same set of vertices) w.r.t. the order \(\mathbf {x}\) such that \(\overline{G(F')}\subseteq G(F)\).

Proof

Let \(\overline{G(F')} := \{(u, v)\mid (u,v)\in G(F), v<u, u\in G(F')~\text{ and }~v\in G(F')\}\). For any u in \(\mathfrak {v}(F')\), the set \(\{(u, v), v<u, v\in \mathfrak {v}(F')\}\) is a also clique since \(\{(u, v)\mid (u,v) \in G(F), v<u, v\in \mathfrak {v}(F)\}\) is a clique by the assumption that F is chordal. Thus \(\overline{G(F')}\) is a chordal completion of \(G(F')\).

3 The Incremental Algorithm Preserves Chordality

In this section, we prove that the incremental algorithm, namely Algorithm 1, proposed in [7] preserves chordality. The main subroutine of Algorithm 1 is the Intersect operation, which takes a polynomial p and a regular chain T as input, and returns a sequence of regular chains \(T_1,\ldots ,T_r\) such that

$$\begin{aligned} V(p)\cap W(T)\subseteq \cup _{i=1}^r W(T_i)\subseteq V(p)\cap \overline{W(T)}, \end{aligned}$$
(1)

where V(p) is the variety of p, W(T) is the quasi-component of T and \(\overline{W(T)}\) is the Zariski closure of W(T). Due to limited space, we refer the reader to [7] for a precise definition of these concepts and a detailed description of the algorithm Intersect and its subroutines Extend, IntersectAlgebraic, IntersectFree, CleanChain, and RegularGcd.

figure a

Lemma 4

One can transform Algorithm Triangularize into an equivalent one with the original flow graph illustrated by the left subgraph of Fig. 2 replaced by the one depicted in the right subgraph of Fig. 2.

Proof

The transformation can be done in two steps. Firstly one can easily replace the direct recursions in Extend, Triangularize and IntersectAlgebraic by iterations. Secondly one can make the function calls to Extend, IntersectAlgebraic, IntersectFree, CleanChain, RegularGcd inline. As a consequence, one obtains an equivalent form of Triangularize with the flow graph of function calls depicted in the right subfig of Fig. 2.

Fig. 2.
figure 2

Transform flow graph of the algorithm.

Full size image

Lemma 5

For each algorithm in Fig. 2, any polynomial in it, if appearing in the output of the algorithm or appearing as the output or input of subroutines in Fig. 2 of the algorithm, is obtained through chordality preserving operations. Moreover, if we remove step 1 in Intersect, which calls prem to test if p belongs to the saturated ideal of T (the algorithm is still correct), all basic operations appearing in the algorithm preserve chordality.

Lemma 6

Let \(F\subset \mathbb {Q}[\mathbf {x}]\) be finite and assume that F is chordal. Let p be a polynomial and T be a regular chain of \(\mathbb {Q}[\mathbf {x}]\) such that \(\mathfrak {G}(p)\subseteq \mathfrak {G}(F)\) and \(\mathfrak {G}(T)\subseteq \mathfrak {G}(F)\). Let \((p_1,T_1),\ldots ,(p_e,T_e)\) be the processes in the output of Intersect or \(\mathsf{Regularize}\), then we have \(\mathfrak {G}(p_i,T_i)\subseteq \mathfrak {G}(F)\). (The output \(T_i\) is treated as a special process \((0, T_i)\).) If this is true, we say that \(\mathsf{Intersect}\) and \(\mathsf{Regularize}\) preserves chordality (w.r.t. F).

Proof

We prove this by induction on the rank of the process (p, T).

  • Base: For each returned process \((p_i,T_i)\), if it is obtained without relying on the output of recursive calls to Intersect or \(\mathsf{Regularize}\), then \(\mathfrak {G}(\{p_i\}\cup T_i)\subseteq \mathfrak {G}(\{p\}\cup T)\) holds.

  • Induction: For each recursive calls to Intersect or \(\mathsf{Regularize}\), the rank of input process is less than that of (p, T). By the induction hypothesis, the recursive calls preserve chordality. Moreover, by Lemma 5, we notice that the input process for each recursive call is obtained by chordality preserving operations as well as the output process of each recursive call is processed by chordality preserving operations. Thus the lemma holds.

Theorem 1

Algorithm Triangularize preserves chordality.

Proof

We prove it by induction on the number of elements of F. The base case trivially holds. Let \(p\in F\) and \(F' := F\setminus \{p\}\). By Lemma 3, there exists a chordal completion \(\overline{G(F')}\) of \(G(F')\) such that \(\overline{G(F')}\subseteq G(F)\). By induction hypothesis, for each regular chain T in the output of the recursive call to \(\mathsf{Triangularize}\), we have \(G(T)\subseteq \overline{G(F')}\subseteq G(F)\). Then the conclusion follows from Lemma 6.

4 Modifying the Implementation of Triangularize

Algorithm 1 has been implemented in the RegularChains library with the same name. After carefully tracing the code, we find that the only operation in the implementation of Triangularize that may destroy the chordality is the pseudo-reminder operation prem. As illustrated by Example 3 in Sect. 2, if two input polynomials do not have the same main variable, prem can destroy chordality. In particular, the operation prem was empolyed in several places for performing the simplification \(q := \mathsf{prem}(p, T)\), where p, q are two polynomials and T is a regular chain. Such simplification does not hurt the correctness of the algorithm, although it may affect the efficiency and should be empolyed with caution. For instance, it was empolyed as a preprocessing step for Intersect but only if the initials of polynomials in T are constants, which may reduce the degree of the polynomial. Note that we have \(V(p)\cap W(T)=V(q)\cap W(T)\), thus the correctness of Intersect is not hurt by Eq. (1). However, if q is involved in producing polynomials as input or output of some algorithms in Fig. 2, then Triangularize may not preserve chordality. Thus, for all these places, we simply do not call prem to preserve chordality. Note that \(q=0\) if and only if p is contained in the saturated ideal of T (membership testing) [6]. If prem is only used for membership testing, we do not suspend the call to prem as it does not affect chordality. There are some other operations, such as iterated resultant, which may not preserve the chordality either. But since they do not produce polynomials as input or output of algorithms in Fig. 2, we keep the calls to them unchanged.

There are several other changes we made to improve the efficiency of the code for chordal input. One is to control the generation of redundant regular chains in Algorithm 1 after each recursive call. Another is to change the order of polynomials in F to solve in Algorithm 1. In the current implementation of Triangularize, one first solves polynomials with smaller rank (in particular with smaller main variables). But this strategy seems to increase the chance of calling operations not preserving chordality. So we instead now first solve polynomials with larger rank. As an example, for lattice-r-10 in Table 1, the two different strategies respectively lead to calling \(\mathsf{prem}(p, T)\) 2659 and 964 times.

The implementation preserving chordality is available in Triangularize in the updated RegularChains library (downloadable from http://www.arcnl.org/cchen/software/chordal) through option \(\mathsf{chordal=true}\).

5 Experiments

Table 2 compares its performance with \(\mathsf{Triangularize}\) in Maple 2019. We also include the performance of the regser command of the Epsilon library as a reference. In Table 1, the examples minor-k, lattice-k and coloring-k are chosen from [11]. The examples minor-r-k (resp. lattice-r-k) is a slight modification of minor-k (resp. lattice-k), but have the same associated graph as minor-k (resp. lattice-k).

Table 1. Benchmark examples.
Full size table

In Table 2, we write \(\mathsf{Triangularize}\) for short as \(\mathsf{Tri}\) and \(\mathsf{Triangularize}\) with \(\mathsf{chordal=true}\) as Tri-C. Denote by K and L respectively the Kalkbrener and Lazard triangular decomposition. For each system F, let n be the number of variables, m be the number of polynomials in F, d be the maximum degree of polynomials in F, t be the computation time (in seconds), c be the number of components in the output. The timeout (−) is set as one hour. As we can see from the table, for these particular sparse systems, Tri-C significantly outperforms \(\mathsf{Tri}\). Meanwhile, Tri-C and regser each have their own favorite examples.

Table 2. Benchmark.
Full size table

6 Conclusion

In this paper, we first proved that the incremental algorithm for computing triangular decompositions proposed in [7] preserves chordality. Then we pointed out that some simplification operations used in the implementation may destroy chordality. We resolve this problem by carefully modifying the implementation in Triangularize and the experimentation shows that significant speedups are obtained for some very sparse polynomial systems. Finally, we remark that more extensive experimentations on diverse polynomial systems are needed to decide the best use of these simplifications with the guidance of theory and possibly the help of artificial intelligence rather than simply relying on experience.