Projects per year
Cylindrical algebraic decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.
|Title of host publication||Mathematical Software – ICMS 2014|
|Subtitle of host publication||4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings|
|Number of pages||8|
|Publication status||Published - 2014|
FingerprintDive into the research topics of 'Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition'. Together they form a unique fingerprint.
- 1 Finished
1/10/11 → 31/12/15
Project: Research council