Appears in collection : 2023 - T3 - WS2 - Geometry of polynomial system solving, optimization and topology

In this talk, I will present the connections between chordal graphs from graph theory and triangular decomposition in top-down style from symbolic computation, including the underlying theories, algorithms, and applications in biology. Viewing triangular decomposition in top-down style as polynomial generalization of Gaussian elimination, we show that all the polynomial sets, including all the computed triangular sets, appearing in several typical top-down algorithms for triangular decomposition have associated graphs which are subgraphs of the chordal graph of the input polynomial set. These theoretical results can be interpreted as “triangular decomposition in top-down style preserves chordality” and are further used to design sparse triangular decomposition for polynomial sets which are sparse with respect to their variables. Sparse triangular decomposition is shown to be more efficient than ordinary one experimentally, and its application on computing equilibria of biological dynamic systems will also be reported. This talk is based on the joint work with Yang Bai, Jiahua Lai, and Wenwen Ju.