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 proceeding

13 Citations (Scopus)
9 Downloads (Pure)

Abstract

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
Pages450-457
Number of pages8
Volume8592 LNCS
ISBN (Print)9783662441985
DOIs
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
http://voronoi.hanyang.ac.kr/icms2014/ (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

Conference

ConferenceInternational Congress on Mathematical Software
Abbreviated titleICMS 2014
CountryKorea, Republic of
CitySeoul
Period5/08/149/08/14
Internet address

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-
662-44199-2_68
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)

Fingerprint 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

    England, M., Bradford, R., Davenport, J. H., & Wilson, D. (2014). Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings (Vol. 8592 LNCS, pp. 450-457). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8592 LNCS). Berlin: Springer Verlag. https://doi.org/10.1007/978-3-662-44199-2_68