Projects per year
Abstract
We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables.
This insight is then combined with an algorithm that produces only fulldimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only fulldimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.
This insight is then combined with an algorithm that produces only fulldimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only fulldimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.
Original language  English 

Title of host publication  Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on 
Publisher  IEEE 
Pages  5360 
Number of pages  8 
ISBN (Print)  9781479984473 
DOIs  
Publication status  Published  2014 
Keywords
 Cylindrical Algebraic Decomposition
 problem formulation
 heuristic
Fingerprint Dive into the research topics of 'Using the distribution of cells by dimension in a cylindrical algebraic decomposition'. Together they form a unique fingerprint.
Projects
 1 Finished

Real Geometry and Connectedness via Triangular Description
Davenport, J., Bradford, R., England, M. & Wilson, D.
Engineering and Physical Sciences Research Council
1/10/11 → 31/12/15
Project: Research council