Sparse Triangular Decomposition for Computing Equilibria of Biological Dynamic Systems Based on Chordal Graphs

Many biological systems are modeled mathematically as dynamic systems in the form of polynomial or rational differential equations. In this paper we apply sparse triangular decomposition to compute the equilibria of biological dynamic systems by exploiting the inherent sparsity of parameter-free systems via the chordal graph and by constructing suitable elimination orderings for parametric systems using the newly introduced block chordal graph. Our experiments with parameter-free systems provide practical information on suitable algorithms for chordal completion and verify the performance gains of sparse triangular decomposition against the ordinary one in the settings of computation of the equilibria. Then we establish full characterizations of block chordal graphs and propose algorithms for testing block chordality and constructing minimal block chordal completions. Based on these results, which are of their own merits in graph theory, we present a new algorithm of sparse triangular decomposition for parametric systems and apply it to detect the equilibria of parametric biological dynamic systems, with remarkable speedups against ordinary triangular decomposition verified by the experiments.