• 论文 • 上一篇    下一篇

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

朱章鹏1,2,陈长波1   

  1. 1. 中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室, 重庆 400714; 2.重庆 邮电大学计算机科学与技术学院, 重庆 400065
  • 出版日期:2020-08-25 发布日期:2020-09-24

朱章鹏,陈长波. 基于机器学习的柱形代数分解变元择序[J]. 系统科学与数学, 2020, 40(8): 1492-1506.

ZHU Zhangpeng, CHEN Changbo. Variable Ordering Selection for Cylindrical Algebraic Decomposition Based on Machine Learning[J]. Journal of Systems Science and Mathematical Sciences, 2020, 40(8): 1492-1506.

Variable Ordering Selection for Cylindrical Algebraic Decomposition Based on Machine Learning

ZHU Zhangpeng 1,2 ,CHEN Changbo1   

  • Online:2020-08-25 Published:2020-09-24

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

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 SuggestVariableOrder.

()
[1] 牟唯嫣,王春玲,赵昕. 基于空间填充准则的交叉验证方法及其应用[J]. 系统科学与数学, 2020, 40(2): 382-388.
[2] 黄志刚,刘佳进,林朝颖. 基于机器学习的上市公司财报舞弊识别前沿方法比较研究[J]. 系统科学与数学, 2020, 40(10): 1882-1900.
[3] 赵金楼,朱辉,刘馨. 基于改进TFIDF的图书馆知识群体特征提取研究[J]. 系统科学与数学, 2019, 39(9): 1450-1461.
[4] 吴迪,林国汉,胡慧,杜先君. 基于指数正则化零空间鉴别分析的故障识别[J]. 系统科学与数学, 2018, 38(10): 1128-1139.
阅读次数
全文


摘要