### 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 truth-table 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.

Original language | English |
---|---|

Title of host publication | Intelligent Computer Mathematics - MKM, Calculemus, DML, and Systems and Projects 2013 - Held as Part of CICM 2013, Proceedings |

Editors | Jacques Carette, David Aspinall, Christoph Lange, Petr Sojka, Wolfgang Windsteiger |

Place of Publication | Heidelberg |

Publisher | Springer |

Pages | 19-34 |

Number of pages | 16 |

Volume | 7961 LNAI |

ISBN (Electronic) | 9783642393204 |

ISBN (Print) | 9783642393198 |

DOIs | |

Publication status | Published - 2013 |

Externally published | Yes |

Event | Conference on Intelligent Computer Mathematics, CICM 2013, Co-located with the MKM 2013, Calculemus 2013, DML 2013, and Systems and Projects 2013 - Bath, United Kingdom Duration: 8 Jul 2013 → 12 Jul 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7961 LNAI |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | Conference on Intelligent Computer Mathematics, CICM 2013, Co-located with the MKM 2013, Calculemus 2013, DML 2013, and Systems and Projects 2013 |
---|---|

Country | United Kingdom |

City | Bath |

Period | 8/07/13 → 12/07/13 |

### Keywords

- cylindrical algebraic decomposition
- Gröbner bases
- problem formulation
- symbolic computation

### ASJC Scopus subject areas

- Computer Science(all)
- Theoretical Computer Science

## Fingerprint Dive into the research topics of 'Optimising problem formulation for cylindrical algebraic decomposition'. Together they form a unique fingerprint.

## Cite this

*Intelligent Computer Mathematics - MKM, Calculemus, DML, and Systems and Projects 2013 - Held as Part of CICM 2013, Proceedings*(Vol. 7961 LNAI, pp. 19-34). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7961 LNAI). Heidelberg: Springer. https://doi.org/10.1007/978-3-642-39320-4_2