### Abstract

Language | English |
---|---|

Title of host publication | Mathematical Software – ICMS 2014 |

Subtitle of host publication | 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings |

Publisher | Springer |

Pages | 450-457 |

Number of pages | 8 |

Volume | 8592 |

ISBN (Print) | 978-3-662-44198-5 |

DOIs | |

Status | Published - 2014 |

### Fingerprint

### Cite this

*Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings*(Vol. 8592, pp. 450-457). Springer. https://doi.org/10.1007/978-3-662-44199-2_68

**Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition.** / England, M; Bradford, R.J.; Davenport, J.H.; Wilson, D.

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

*Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings.*vol. 8592, Springer, pp. 450-457. https://doi.org/10.1007/978-3-662-44199-2_68

}

TY - GEN

T1 - Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition

AU - England, M

AU - Bradford, R.J.

AU - Davenport, J.H.

AU - Wilson, D.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://dx.doi.org/10.1007/978-3-662-44199-2_68

U2 - 10.1007/978-3-662-44199-2_68

DO - 10.1007/978-3-662-44199-2_68

M3 - Conference contribution

SN - 978-3-662-44198-5

VL - 8592

SP - 450

EP - 457

BT - Mathematical Software – ICMS 2014

PB - Springer

ER -