@inproceedings{d893ed80df6d468b9403acf1dee34fd7,
title = "Analyses and Implementations of Chordality-Preserving Top-Down Algorithms for Triangular Decomposition",
abstract = "When the input polynomial set has a chordal associated graph, top-down algorithms for triangular decomposition are proved to preserve the chordal structure. Based on these theoretical results, sparse algorithms for triangular decomposition were proposed and demonstrated with experiments to be more efficient in case of sparse polynomial sets. However, existing implementations of top-down triangular decomposition are not guaranteed to be chordality-preserving due to operations which potentially destroy the chordality. In this paper, we first analyze the current implementations of typical top-down algorithms for triangular decomposition in the Epsilon package to identify these chordality-destroying operations. Then modifications are made accordingly to guarantee new implementations of such algorithms are chordality-preserving. In particular, the technique of dynamic checking is introduced to ensure that the modifications also keep the computational efficiency. Experimental results with polynomial sets from biological systems are also reported.",
keywords = "Chordal graph, Implementation, Sparsity, Triangular decomposition",
author = "Mingyu Dong and Chenqi Mou",
note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 24th International Workshop on Computer Algebra in Scientific Computing, CASC 2022 ; Conference date: 22-08-2022 Through 26-08-2022",
year = "2022",
doi = "10.1007/978-3-031-14788-3\_8",
language = "英语",
isbn = "9783031147876",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "124--142",
editor = "Fran{\c c}ois Boulier and Matthew England and Sadykov, \{Timur M.\} and Vorozhtsov, \{Evgenii V.\}",
booktitle = "Computer Algebra in Scientific Computing - 24th International Workshop, CASC 2022, Proceedings",
address = "德国",
}