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

Matthew England, Russell Bradford, James H. Davenport, David Wilson

Research output: Chapter in Book/Report/Conference proceedingConference proceedingpeer-review

16 Citations (Scopus)
26 Downloads (Pure)


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.

Original languageEnglish
Title of host publicationMathematical Software, ICMS 2014 - 4th International Congress, Proceedings
Place of PublicationBerlin
PublisherSpringer Verlag
Number of pages8
Volume8592 LNCS
ISBN (Print)9783662441985
Publication statusPublished - 2014
Externally publishedYes
EventInternational Congress on Mathematical Software - Hanyang University, Seoul, Korea, Republic of
Duration: 5 Aug 20149 Aug 2014
Conference number: 4 (Link to conference website)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8592 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


ConferenceInternational Congress on Mathematical Software
Abbreviated titleICMS 2014
Country/TerritoryKorea, Republic of
Internet address

Bibliographical note

The final publication is available at Springer via
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.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this