报告题目: Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure

报 告 人: 夏壁灿 教授（北京大学）

报告时间：2023年6月15日（星期四）20:00-21:00

报告地点：海山楼A1101

报告校内联系人：黄辉 副教授  联系方式：huanghui@dlut.edu.cn

报告摘要：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 talk, 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.

报告人简介：夏壁灿，北京大学数学科学学院教授，中国工业与应用数学学会常务理事，中国数学会计算机数学专委会副主任。曾担任北京大学数学科学学院副院长，北京大学数学科学学院信息科学系主任。 研究兴趣包括：符号计算，程序与混成系统验证，自动定理证明。