Abstract: Cylindrical algebraic decomposition (CAD) is a widely used approach for computing the real solutions of polynomial systems.The choice of variable ordering has a significant impact on its computation time.Most of existing ordering selection algorithms are based on heuristic empirical algorithms,whose accuracy are not high.A few approaches based on machine learning use small data sets and are based on complex human characteristics.In this paper,on the basis of randomly generating a large set of polynomial systems,which are tagged with timings obtained by applying different orderings for computing CAD,a new kind of explicit representation feature and a new hierarchical neural network are proposed.Firstly,according to the computation time of CAD with the worst ordering,the data set is divided into four subsets with different computation difficulties,and the classification models are established respectively.Secondly,a regression model for predicting the longest computation time is built.Finally,the longest computation time is predicted according to the regression model,based on which a classification model with right computation difficulty is automatically selected to predict the optimal variable ordering.Experimental results show that the performance of explicit features is better than that of complex handcrafted features,and the performance of the optimal ordering predicted by hierarchical neural network on difficult problems is about two times better than that of an empirical algorithm.

Key words: Cylindrical algebraic decomposition, Feature selection, Hierarchical neural network, Regression, Variable ordering