Abstract for the talk on 01.11.2018 (10:00 h)

Seminar on Nonlinear Algebra

Chenqi Mou (Beihang University Beijing)
Chordal Graphs in Triangular Decomposition in Top-Down Style

In this talk we present some underlying connections between symbolic computation and graph theory. Inspired by the two papers of Cifuentes and Parrilo in 2016 and 2017, we are interested in the chordal graph structures of polynomial sets appearing in triangular decomposition in top-down style. Viewing triangular decomposition in top-down style as multivariate generalization of Gaussian elimination, we show that the associated graph of one specific triangular set computed in any algorithm for triangular decomposition in top-down style is a subgraph of the chordal graph of the input polynomial set and that all the polynomial sets, including all the computed triangular sets, appearing in one specific algorithm for triangular decomposition in top-down style (Wang’s method) have associated graphs which are subgraphs of the chordal graph of the input polynomial set. Potential applications of chordal graphs in symbolic computation are also discussed.