Using the distribution of cells by dimension in a cylindrical algebraic decomposition

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

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

8 Downloads (Pure)

Abstract

We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables. This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.

Original languageEnglish
Title of host publicationProceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages53-60
Number of pages8
ISBN (Electronic)9781479984480
DOIs
Publication statusPublished - 5 Feb 2015
Externally publishedYes
Event16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing - Timisoara, Romania
Duration: 22 Sep 201425 Sep 2014
Conference number: 16

Conference

Conference16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Abbreviated titleSYNASC 2014
CountryRomania
CityTimisoara
Period22/09/1425/09/14

Bibliographical note

© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

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.

Keywords

  • cell distribution
  • cylindrical algebraic decomposition
  • heuristic
  • problem formulation

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Using the distribution of cells by dimension in a cylindrical algebraic decomposition'. Together they form a unique fingerprint.

  • Cite this

    Wilson, D., England, M., Bradford, R., & Davenport, J. H. (2015). Using the distribution of cells by dimension in a cylindrical algebraic decomposition. In Proceedings - 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014 (pp. 53-60). [7034665] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SYNASC.2014.15