Chordality Preserving Incremental Triangular Decomposition and Its Implementation

In this paper, we first prove that the incremental algorithm for computing triangular decompositions proposed by Chen and Moreno Maza in ISSAC’ 2011 in its original form preserves chordality, which is an important property on sparsity of variables. On the other hand, we find that the current implementation in Triangularize command of the RegularChains library in Maple may not always respect chordality due to the use of some simplification operations. Experimentation show that modifying these operations, together with some other optimizations, brings significant speedups for some super sparse polynomial systems.