### Abstract

Cylindrical algebraic decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.

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

Title of host publication | Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings |

Publisher | Springer Verlag |

Pages | 45-60 |

Number of pages | 16 |

Volume | 8543 |

Edition | LNCS |

ISBN (Electronic) | 978-3-319-08434-3 |

ISBN (Print) | 978-3-319-08433-6 |

DOIs | |

Publication status | Published - 2014 |

Externally published | Yes |

Event | 2014 International Conference on Intelligent Computer Mathematics - Coimbra, Portugal Duration: 7 Jul 2014 → 11 Jul 2014 |

### Publication series

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

Volume | 8543 LNAI |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | 2014 International Conference on Intelligent Computer Mathematics |
---|---|

Abbreviated title | CICM 2014 |

Country | Portugal |

City | Coimbra |

Period | 7/07/14 → 11/07/14 |

### Fingerprint

### Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3319-08434-3_5Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

### Keywords

- cylindrical algebraic decomposition
- problem formulation
- regular chains
- triangular decomposition
- truth table invariance

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings*(LNCS ed., Vol. 8543 , pp. 45-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8543 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-08434-3_5

**Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition.** / England, Matthew; Bradford, Russell; Chen, Changbo; Davenport, James H.; Maza, Marc Moreno; Wilson, David.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding

*Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings.*LNCS edn, vol. 8543 , Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8543 LNAI, Springer Verlag, pp. 45-60, 2014 International Conference on Intelligent Computer Mathematics, Coimbra, Portugal, 7/07/14. https://doi.org/10.1007/978-3-319-08434-3_5

}

TY - GEN

T1 - Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition

AU - England, Matthew

AU - Bradford, Russell

AU - Chen, Changbo

AU - Davenport, James H.

AU - Maza, Marc Moreno

AU - Wilson, David

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3319-08434-3_5 Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

PY - 2014

Y1 - 2014

N2 - Cylindrical algebraic decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.

AB - Cylindrical algebraic decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.

KW - cylindrical algebraic decomposition

KW - problem formulation

KW - regular chains

KW - triangular decomposition

KW - truth table invariance

U2 - 10.1007/978-3-319-08434-3_5

DO - 10.1007/978-3-319-08434-3_5

M3 - Conference proceeding

SN - 978-3-319-08433-6

VL - 8543

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

SP - 45

EP - 60

BT - Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings

PB - Springer Verlag

ER -