基于机器学习的柱形代数分解变元择序

Variable Ordering Selection for Cylindrical Algebraic Decomposition Based on Machine Learning

柱形代数分解(cylindrical algebraic decomposition,CAD)是计算实代数几何的基本工具之一,在很多领域都有重要应用.理论和实践表明不同的变元序对CAD的计算效率影响很大.已有的CAD的选序算法基本上是根据经验来选择,也有学者研究了用机器学习的方法来选择不同的经验选序算法.和已有方法不同,文章用机器学习的方法直接选择变元序.文章基于多项式组的图结构,提出了一组新的特征.实验表明利用这些特征训练出的多分类器预测最佳变元序的能力不仅明显优于随机择序,也优于Maple命令Suggest VariableOrder实现的传统启发式方法.

Cylindrical algebraic decomposition(CAD)is one of the basic tools in computational real algebraic geometry.It has important applications in many fields.It’s shown in both theory and practice that different variable orders have a great influence on the efficiency of CAD.Most of the existing algorithms for selecting variable orders for CAD are based on experience.Recently,some scholars have studied applying machine learning methods to select best empirical methods for variable order selection.Different from the existing methods,we apply machine learning to select variable order directly.Based on a graph structure of the polynomial system,we propose a group of new features.Experiments show that the multi-classifier trained with these features outperforms not only the random order selection method,but also the traditional heuristic method implemented by Maple command of Suggest VariableOrder.