You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


Introduction {#Sec1}
============

The method of triangular decomposition pioneered by Ritt \[[@CR19]\] and Wu \[[@CR23]\] 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 \[[@CR1], [@CR2], [@CR14], [@CR15], [@CR25]\] and algorithms \[[@CR7], [@CR10], [@CR12], [@CR13], [@CR16], [@CR17], [@CR22], [@CR24]\]. 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 \[[@CR24]\] and comprehensive triangular decomposition of parametric semi-algebraic sets \[[@CR5]\], computing sample points of semi-algebraic sets \[[@CR4]\], describing semi-algebraic sets \[[@CR4]\], as well as computing cylindrical algebraic decompositions and performing quantifier elimination \[[@CR3], [@CR8], [@CR9]\]. 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 \[[@CR11]\] 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 \[[@CR20]\] and semidefinite optimization \[[@CR21]\].

It has already been shown that some top-down algorithms \[[@CR22]\] (up to minor modification of its original form) preserve chordality \[[@CR18]\]. Incremental algorithms \[[@CR7], [@CR16], [@CR17]\] 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 \[[@CR6], [@CR7]\]. 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.

Basic Lemmas {#Sec2}
============

Definition 1 {#FPar1}
------------

**(Graph).** Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}=x_1,\ldots ,x_n$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F\subset \mathbf {k}[\mathbf {x}]$$\end{document}$. The (associated) graph $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ of *F* is an undirected graph defined as follows:The set *V* of vertices of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ is the set of variables appearing in *F*.The set *E* of edges of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ is the set of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$(x_i, x_j)$$\end{document}$, $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$i\ne j$$\end{document}$, where $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_i$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_j$$\end{document}$ simultaneously appear in some $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$f\in F$$\end{document}$.

Denote by $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {v}(\mathfrak {G}(F))$$\end{document}$ an operation which returns *V*.

Definition 2 {#FPar2}
------------

**(Perfect elimination ordering).** Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}=(V, E)$$\end{document}$ be a graph with vertices $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$V=\{x_1,\ldots ,x_n\}$$\end{document}$. An ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}=x_{i_1}>\cdots >x_{i_n}$$\end{document}$ is a perfect elimination ordering for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}$$\end{document}$ if for any $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_{i_j}$$\end{document}$, the induced subgraph on the set of vertices $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$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\}$$\end{document}$ is a clique. If a perfect elimination ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$ exists for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}$$\end{document}$, we say $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}$$\end{document}$ is chordal (w.r.t. $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$). We say that a graph $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}}$$\end{document}$ with vertices $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$V=\{x_1,\ldots ,x_n\}$$\end{document}$ is a chordal completion of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}$$\end{document}$, if $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}}$$\end{document}$ is chordal and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}$$\end{document}$ is a subgraph of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}}$$\end{document}$.

Example 1 {#FPar3}
---------

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F := \{x_1^2-x_2^2+x_2x_4, x_2^2-x_3x_4\}$$\end{document}$. Then $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ is illustrated in Fig. [1](#Fig1){ref-type="fig"}, where the vertex $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_i$$\end{document}$ is renamed as *i* for short. The ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_1>x_2>x_3>x_4$$\end{document}$ is a perfect elimination ordering and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}$$\end{document}$ is chordal w.r.t. this ordering. Another ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_2>x_1>x_3>x_4$$\end{document}$ is not a perfect elimination ordering.

Fig. 1.Chordal graph.

Definition 3 {#FPar4}
------------

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$ be a given ordering and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F\subset \mathbf {k}[\mathbf {x}]$$\end{document}$. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$M:2^{\mathbf {k}[\mathbf {x}]}\rightarrow 2^{2^{\mathbf {k}[\mathbf {x}]}}$$\end{document}$. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}(F)}$$\end{document}$ be any chordal completion of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ w.r.t. the ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$ (that is $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$ is a perfect elimination ordering for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}(F)}$$\end{document}$). We say that *M* preserves chordality in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ (resp. $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}(F)}$$\end{document}$) if for any $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$S\in M(F)$$\end{document}$, we have $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(S)\subseteq \mathfrak {G}(F)$$\end{document}$ (resp. $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(S)\subseteq \overline{\mathfrak {G}(F)}$$\end{document}$). 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 $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ w.r.t. $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$, we say that *M* preserves chordality (for *F*).

Remark 1 {#FPar5}
--------

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$O:\mathbf {k}[\mathbf {x}]\rightarrow 2^{\mathbf {k}[\mathbf {x}]}$$\end{document}$ be a unary operation which maps $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$f\in \mathbf {k}[\mathbf {x}]$$\end{document}$ to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$O(f)\subset \mathbf {k}[\mathbf {x}]$$\end{document}$. Then it induces a map *M* which maps $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{f\}$$\end{document}$ to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{O(f)\}$$\end{document}$. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$O:\mathbf {k}[\mathbf {x}]\times \mathbf {k}[\mathbf {x}]\rightarrow 2^{\mathbf {k}[\mathbf {x}]}$$\end{document}$ be a binary operation which maps (*f*, *g*) to *O*(*f*, *g*). Then it induces a map *M* which maps $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{f,g\}$$\end{document}$ to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{O(f,g)\}$$\end{document}$. For both cases, if *M* (strongly) preserves chordality, we say that the operation *O* (strongly) preserves chordality.

Example 2 {#FPar6}
---------

Consider $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$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}\}$$\end{document}$. Figure [1](#Fig1){ref-type="fig"} depicts a chordal completion $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}(F)}$$\end{document}$ of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(F)$$\end{document}$ w.r.t. the ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_1>x_2>x_3>x_4$$\end{document}$. Let *M* be the Triangularize command in Maple 2019, which computes a set of regular chains as follows:$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$ \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} $$\end{document}$$As we see, it does not preserve chordality since the graph of the fifth regular chain is not a subgraph of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}(F)}$$\end{document}$.

Definition 4 {#FPar7}
------------

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$O:K[\mathbf {x}]\rightarrow 2^{K[\mathbf {x}]}$$\end{document}$ be a unary operation. We say that it respects the (elimination) ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$ for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$f\in \mathbf {k}[\mathbf {x}]$$\end{document}$ if $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {v}(O(f))\subseteq \mathfrak {v}(f)$$\end{document}$.

Lemma 1 {#FPar8}
-------

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

Proof {#FPar9}
-----

It trivially holds since $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(f)$$\end{document}$ is a clique for any $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$f\in \mathbf {k}[\mathbf {x}]$$\end{document}$.

Definition 5 {#FPar10}
------------

Given $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$f\in \mathbf {k}[\mathbf {x}]$$\end{document}$, let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\text{ mvar }(f)$$\end{document}$ be the largest variable appearing in *f*. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$O:\mathbf {k}[\mathbf {x}]\times \mathbf {k}[\mathbf {x}]\rightarrow 2^{\mathbf {k}[\mathbf {x}]}$$\end{document}$ be a binary operation. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$S := O(f, g)$$\end{document}$. We say that *O* respects the ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$ (for *f* and *g*) if the following are satisfied:If $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\text{ mvar }(f)=\text{ mvar }(g)$$\end{document}$, we have $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {v}(S)\subseteq \mathfrak {v}(\{f, g\})$$\end{document}$.If $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\text{ mvar }(f)\ne \text{ mvar }(g)$$\end{document}$, we have $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {v}(S)\subseteq \mathfrak {v}(f)$$\end{document}$ or $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {v}(S)\subseteq \mathfrak {v}(g)$$\end{document}$.

Lemma 2 {#FPar11}
-------

Suppose that *O* respects the ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$, then we have the following.

If $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\text{ mvar }(f)\ne \text{ mvar }(g)$$\end{document}$, then *O* strongly preserves chordality.If $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\text{ mvar }(f)=\text{ mvar }(g)$$\end{document}$, then *O* preserves chordality.

Proof {#FPar12}
-----

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}}$$\end{document}$ be any chordal completion of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(\{f,g\})$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_i$$\end{document}$ be the common main variable of *f* and *g*. By the definition of chordal graph, the subgraph of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{\mathfrak {G}}$$\end{document}$ induced by the set of vertices $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {v}(\overline{\mathfrak {G}})\setminus \{x_i\}$$\end{document}$ is a clique. So the conclusion holds.

Corollary 1 {#FPar13}
-----------

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](#FPar14){ref-type="sec"}.

Example 3 {#FPar14}
---------

Consider the system $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F:=\{f_1,f_2\}$$\end{document}$ again from Example [1](#FPar3){ref-type="sec"} and the ordering $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$x_1>x_2>x_3>x_4$$\end{document}$. We have $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\text{ mvar }(f_1)=x_1$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\text{ mvar }(f_2)=x_2$$\end{document}$. Then $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{prem}(f_1,f_2,x_2)={x_{{1}}}^{2}+x_{{2}}x_{{4}}-x_{{3}}x_{{4}}$$\end{document}$. Clearly prem does not preserve chordality for $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$f_1$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$f_2$$\end{document}$.

Lemma 3 {#FPar15}
-------

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F\subset \mathbb {Q}[\mathbf {x}]$$\end{document}$. Let *p* be a polynomial in *F*. Assume that *F* is chordal w.r.t. the variable order $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F' := F\setminus \{p\}$$\end{document}$. Then there exists a chordal completion $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{G(F')}$$\end{document}$ of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$G(F')$$\end{document}$ (with the same set of vertices) w.r.t. the order $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbf {x}$$\end{document}$ such that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{G(F')}\subseteq G(F)$$\end{document}$.

Proof {#FPar16}
-----

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{G(F')} := \{(u, v)\mid (u,v)\in G(F), v<u, u\in G(F')~\text{ and }~v\in G(F')\}$$\end{document}$. For any *u* in $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {v}(F')$$\end{document}$, the set $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{(u, v), v<u, v\in \mathfrak {v}(F')\}$$\end{document}$ is a also clique since $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{(u, v)\mid (u,v) \in G(F), v<u, v\in \mathfrak {v}(F)\}$$\end{document}$ is a clique by the assumption that *F* is chordal. Thus $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{G(F')}$$\end{document}$ is a chordal completion of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$G(F')$$\end{document}$.

The Incremental Algorithm Preserves Chordality {#Sec3}
==============================================

In this section, we prove that the incremental algorithm, namely Algorithm 1, proposed in \[[@CR7]\] 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 $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$T_1,\ldots ,T_r$$\end{document}$ such that$$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\begin{aligned} V(p)\cap W(T)\subseteq \cup _{i=1}^r W(T_i)\subseteq V(p)\cap \overline{W(T)}, \end{aligned}$$\end{document}$$where *V*(*p*) is the variety of *p*, *W*(*T*) is the quasi-component of *T* and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{W(T)}$$\end{document}$ is the Zariski closure of *W*(*T*). Due to limited space, we refer the reader to \[[@CR7]\] for a precise definition of these concepts and a detailed description of the algorithm Intersect and its subroutines Extend, IntersectAlgebraic, IntersectFree, CleanChain, and RegularGcd.

Lemma 4 {#FPar17}
-------

One can transform Algorithm Triangularize into an equivalent one with the original flow graph illustrated by the left subgraph of Fig. [2](#Fig2){ref-type="fig"} replaced by the one depicted in the right subgraph of Fig. [2](#Fig2){ref-type="fig"}.

Proof {#FPar18}
-----

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](#Fig2){ref-type="fig"}.

Fig. 2.Transform flow graph of the algorithm.

Lemma 5 {#FPar19}
-------

For each algorithm in Fig. [2](#Fig2){ref-type="fig"}, any polynomial in it, if appearing in the output of the algorithm or appearing as the output or input of subroutines in Fig. [2](#Fig2){ref-type="fig"} 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 {#FPar20}
-------

Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F\subset \mathbb {Q}[\mathbf {x}]$$\end{document}$ be finite and assume that *F* is chordal. Let *p* be a polynomial and *T* be a regular chain of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathbb {Q}[\mathbf {x}]$$\end{document}$ such that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(p)\subseteq \mathfrak {G}(F)$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(T)\subseteq \mathfrak {G}(F)$$\end{document}$. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$(p_1,T_1),\ldots ,(p_e,T_e)$$\end{document}$ be the processes in the output of Intersect or $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Regularize}$$\end{document}$, then we have $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(p_i,T_i)\subseteq \mathfrak {G}(F)$$\end{document}$. (The output $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$T_i$$\end{document}$ is treated as a special process $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$(0, T_i)$$\end{document}$.) If this is true, we say that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Intersect}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Regularize}$$\end{document}$ preserves chordality (w.r.t. *F*).

Proof {#FPar21}
-----

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

*Base:* For each returned process $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$(p_i,T_i)$$\end{document}$, if it is obtained without relying on the output of recursive calls to Intersect or $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Regularize}$$\end{document}$, then $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathfrak {G}(\{p_i\}\cup T_i)\subseteq \mathfrak {G}(\{p\}\cup T)$$\end{document}$ holds.*Induction:* For each recursive calls to Intersect or $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Regularize}$$\end{document}$, 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](#FPar19){ref-type="sec"}, 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 {#FPar22}
---------

Algorithm Triangularize preserves chordality.

Proof {#FPar23}
-----

We prove it by induction on the number of elements of *F*. The base case trivially holds. Let $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$p\in F$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$F' := F\setminus \{p\}$$\end{document}$. By Lemma [3](#FPar15){ref-type="sec"}, there exists a chordal completion $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{G(F')}$$\end{document}$ of $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$G(F')$$\end{document}$ such that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\overline{G(F')}\subseteq G(F)$$\end{document}$. By induction hypothesis, for each regular chain *T* in the output of the recursive call to $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Triangularize}$$\end{document}$, we have $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$G(T)\subseteq \overline{G(F')}\subseteq G(F)$$\end{document}$. Then the conclusion follows from Lemma [6](#FPar20){ref-type="sec"}.

Modifying the Implementation of Triangularize {#Sec4}
=============================================

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](#FPar14){ref-type="sec"} in Sect. [2](#Sec2){ref-type="sec"}, 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 $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$q := \mathsf{prem}(p, T)$$\end{document}$, 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 $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$V(p)\cap W(T)=V(q)\cap W(T)$$\end{document}$, thus the correctness of Intersect is not hurt by Eq. ([1](#Equ1){ref-type=""}). However, if *q* is involved in producing polynomials as input or output of some algorithms in Fig. [2](#Fig2){ref-type="fig"}, then Triangularize may not preserve chordality. Thus, for all these places, we simply do not call prem to preserve chordality. Note that $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$q=0$$\end{document}$ if and only if *p* is contained in the saturated ideal of *T* (membership testing) \[[@CR6]\]. 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](#Fig2){ref-type="fig"}, 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](#Tab1){ref-type="table"}, the two different strategies respectively lead to calling $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{prem}(p, T)$$\end{document}$ 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 $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{chordal=true}$$\end{document}$.

Experiments {#Sec5}
===========

Table [2](#Tab2){ref-type="table"} compares its performance with $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Triangularize}$$\end{document}$ in Maple 2019. We also include the performance of the regser command of the Epsilon library as a reference. In Table [1](#Tab1){ref-type="table"}, the examples minor-*k*, lattice-*k* and coloring-*k* are chosen from \[[@CR11]\]. 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.minor-*k*$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{x_{2i-1}x_{2i+2}-x_{2i}x_{2i+1}\mid i=1,\ldots ,k\}$$\end{document}$minor-r-*k*$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{x_{2i-1}x_{2i+2}-x_{2i}x_{2i+1}+x_{2i}+x_{2i+1}\mid i=1,\ldots ,k\}$$\end{document}$lattice-*k*$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{x_{i}x_{i+3}-x_{i+1}x_{i+2}\mid i=1,\ldots ,k\}$$\end{document}$lattice-r-*k*$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{x_{i}x_{i+3}-x_{i+1}x_{i+2}+x_{i+3}^2\mid i=1,\ldots ,k\}$$\end{document}$coloring-*k*$\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\{x_{i}^3-1\mid i=1,\ldots ,k\}\cup \{\sum _{j=0}^2x_{i}^{2-j}x_{(i \text{ mod } k) + 1}^j\mid i=1,\ldots ,k\}$$\end{document}$

In Table [2](#Tab2){ref-type="table"}, we write $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Triangularize}$$\end{document}$ for short as $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Tri}$$\end{document}$ and $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Triangularize}$$\end{document}$ with $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{chordal=true}$$\end{document}$ 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 $\documentclass[12pt]{minimal}
                \usepackage{amsmath}
                \usepackage{wasysym} 
                \usepackage{amsfonts} 
                \usepackage{amssymb} 
                \usepackage{amsbsy}
                \usepackage{mathrsfs}
                \usepackage{upgreek}
                \setlength{\oddsidemargin}{-69pt}
                \begin{document}$$\mathsf{Tri}$$\end{document}$. Meanwhile, Tri-C and regser each have their own favorite examples.Table 2.Benchmark.Sys*nmd*regserTri (K)Tri (L)Tri-C (K)Tri-C (L)Time*c*Time*c*Time*c*Time*c*Time*c*minor-10221022.33445527.0889467.68756.7388924.75767minor-153215286.1382361701.9987−−1147.7987−−minor-18381821402.146810−−−−−−−−minor-2042202−−−−−−−−−−minor-r-102210232.05221410.721227.04981.700111.98351minor-r-1226122336.71166741.3011859.617135.366175.511081minor-r-1430142−−153.41−−17.871584.83329minor-r-1532152−−−−−−33.2311762.45842lattice-10131020.140187.065157.6150.417240.41724lattice-20232021.640154−−−−8.931878.913187lattice-303330219.471285−−−−409.41549406.21549lattice-4043402259.610733−−−−−−−−lattice-r-10131020.4591321.41126.27130.43610.50613lattice-r-151815227.1918−−−−2.13412.29718lattice-r-1821182−−−−−−150.21152.721lattice-r-2023202−−−−−−−−−−coloring-10102036.4512313.451239.891234.9161024.636102coloring-121224356.8732292.6732256.9632223.0626722.79267coloring-1414283986.5843667.7843380.1843128.8699130.2699coloring-1515303−−−−−−315.71131312.71131

Conclusion {#Sec6}
==========

In this paper, we first proved that the incremental algorithm for computing triangular decompositions proposed in \[[@CR7]\] 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.

The authors would like to thank anonymous referees for helpful comments. This research was supported by NSFC (11771421, 11671377, 61572024), CAS "Light of West China" Program, the Key Research Program of Frontier Sciences of CAS (QYZDB-SSW-SYS026), and cstc2018jcyj-yszxX0002 of Chongqing.