基于分级神经网络的柱形代数分解变元序选择

柱形代数分解是广泛应用于求多项式系统实数解的一种计算方法。不同的变元序对其计算时间有显著影响。已有选序算法多基于启发式的经验算法,准确率不高。少数基于机器学习的方法使用的数据集较小,且基于复杂人工特征。文中在随机生成大量多项式系统与所有序计算时间标注的数据基础上,提出一类新的多项式显性表示特征和一种新的分级神经网络。首先根据最差序计算时间将数据集划分成4个不同计算难度的子集并分别建立预测最优序的分类模型,其次建立预测最长计算时间的回归模型,最后根据回归模型预测最长计算时间并据其自动选择相应难度分类模型预测最优变元序。实验结果表明,显性特征的性能优于复杂人工特征,且在困难问题上分级神经网络所预测最优序的性能约为经验选序算法的3倍。

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

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