Cargando…

Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks

Cylindrical algebraic decomposition (CAD) is a fundamental tool in computational real algebraic geometry. Previous studies have shown that machine learning (ML) based approaches may outperform traditional heuristic ones on selecting the best variable ordering when the number of variables [Formula: s...

Descripción completa

Detalles Bibliográficos
Autores principales: Chen, Changbo, Zhu, Zhangpeng, Chi, Haoyu
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7340889/
http://dx.doi.org/10.1007/978-3-030-52200-1_28
_version_ 1783555114923982848
author Chen, Changbo
Zhu, Zhangpeng
Chi, Haoyu
author_facet Chen, Changbo
Zhu, Zhangpeng
Chi, Haoyu
author_sort Chen, Changbo
collection PubMed
description Cylindrical algebraic decomposition (CAD) is a fundamental tool in computational real algebraic geometry. Previous studies have shown that machine learning (ML) based approaches may outperform traditional heuristic ones on selecting the best variable ordering when the number of variables [Formula: see text]. One main challenge for handling the general case is the exponential explosion of number of different orderings when n increases. In this paper, we propose an iterative method for generating candidate variable orderings and an ML approach for selecting the best ordering from them via learning neural network classifiers. Experimentations show that this approach outperforms heuristic ones for [Formula: see text].
format Online
Article
Text
id pubmed-7340889
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-73408892020-07-08 Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks Chen, Changbo Zhu, Zhangpeng Chi, Haoyu Mathematical Software – ICMS 2020 Article Cylindrical algebraic decomposition (CAD) is a fundamental tool in computational real algebraic geometry. Previous studies have shown that machine learning (ML) based approaches may outperform traditional heuristic ones on selecting the best variable ordering when the number of variables [Formula: see text]. One main challenge for handling the general case is the exponential explosion of number of different orderings when n increases. In this paper, we propose an iterative method for generating candidate variable orderings and an ML approach for selecting the best ordering from them via learning neural network classifiers. Experimentations show that this approach outperforms heuristic ones for [Formula: see text]. 2020-06-06 /pmc/articles/PMC7340889/ http://dx.doi.org/10.1007/978-3-030-52200-1_28 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Chen, Changbo
Zhu, Zhangpeng
Chi, Haoyu
Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks
title Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks
title_full Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks
title_fullStr Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks
title_full_unstemmed Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks
title_short Variable Ordering Selection for Cylindrical Algebraic Decomposition with Artificial Neural Networks
title_sort variable ordering selection for cylindrical algebraic decomposition with artificial neural networks
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7340889/
http://dx.doi.org/10.1007/978-3-030-52200-1_28
work_keys_str_mv AT chenchangbo variableorderingselectionforcylindricalalgebraicdecompositionwithartificialneuralnetworks
AT zhuzhangpeng variableorderingselectionforcylindricalalgebraicdecompositionwithartificialneuralnetworks
AT chihaoyu variableorderingselectionforcylindricalalgebraicdecompositionwithartificialneuralnetworks