Details:
Title  Optimising problem formulation for cylindrical algebraic decomposition.  Author(s)  James H. Davenport, Wilson David, England Matthew, Bradford Russell  Type  Book, Chapter in Book, Conference Proceeding  Abstract  Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing: the variable ordering for a CAD problem, a designated equational constraint, and formulations for truthtable invariant CADs (TTICADs). We then consider the possibility of using Gröbner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.  Keywords  cylindrical algebraic decomposition, problem formulation, Gröbner bases, symbolic computation  ISBN  9783642393198/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642393204_2 
Language  English  Pages  1934  Publisher  Berlin: Springer  Year  2013  Edition  0  Translation 
No  Refereed 
No 
