Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure. (May 2023)

• Record Type: Journal Article
• Authors: Li, Haokun; Xia, Bican; Zhang, Huiying; Zheng, Tao
• Is Part Of: Journal of symbolic computation. Volume 116(2023)
• Page Start: 324
• Page End: 344
• Publication Date: 2023-05
• Subjects: Cylindrical algebraic decomposition -- Variable ordering -- Chordality -- Polynomial; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.10.009
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: As is well-known, the choice of variable ordering while computing cylindrical algebraic decomposition (CAD) has a great effect on the time and memory use of the computation as well as the number of sample points computed. In this paper, we indicate that typical CAD algorithms, if executed with respect to a special kind of variable orderings (called "the perfect elimination orderings", PEO), naturally preserve chordality, which is well compatible with an important (variable) sparsity pattern called "the correlative sparsity". If the associated graph of the polynomial system in question is chordal ( resp., is nearly chordal), then a PEO of the associated graph ( resp., of a minimal chordal completion of the associated graph) can be a better variable ordering for the CAD computation than other naive variable orderings in the sense that it results in a much smaller full set of projection polynomials and thus more efficient computation. A new ( m, d ) -property of the full set of CAD projection polynomials obtained via a PEO is given, which indicates that when the corresponding perfect elimination tree has a lower height, the full set of projection polynomials also tends to have a smaller "size". Furthermore, combining the lower-tree-height rule with Brown's heuristics, a new procedure is proposed to choose better PEOs for CAD computation.