Published in

Springer Verlag, Lecture Notes in Computer Science, p. 92-107

DOI: 10.1007/978-3-319-08434-3_8

Links

Tools

Export citation

Search in Google Scholar

Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition

Journal article published in 2014 by Zongyan Huang, Matthew England, David Wilson, James H. Davenport, Lawrence C. Paulson, James Bridge
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

Cylindrical algebraic decomposition(CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. When using CAD, there is often a choice for the ordering placed on the variables. This can be important, with some problems infeasible with one variable ordering but easy with another. Machine learning is the process of fitting a computer model to a complex function based on properties learned from measured data. In this paper we use machine learning (specifically a support vector machine) to select between heuristics for choosing a variable ordering, outperforming each of the separate heuristics. ; Comment: 16 pages