### Abstract

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 language | English |
---|---|

Title of host publication | Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on |

Publisher | IEEE |

Pages | 53-60 |

Number of pages | 8 |

ISBN (Print) | 978-1-4799-8447-3 |

DOIs | |

Publication status | Published - 2014 |

### Fingerprint

### Keywords

- Cylindrical Algebraic Decomposition
- problem formulation
- heuristic

### Cite this

*Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on*(pp. 53-60). IEEE. https://doi.org/10.1109/SYNASC.2014.15

**Using the distribution of cells by dimension in a cylindrical algebraic decomposition.** / Wilson, D.; England, M; Bradford, R.J.; Davenport, J.H.

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

*Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on.*IEEE, pp. 53-60. https://doi.org/10.1109/SYNASC.2014.15

}

TY - GEN

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

AU - Wilson, D.

AU - England, M

AU - Bradford, R.J.

AU - Davenport, J.H.

PY - 2014

Y1 - 2014

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

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

KW - Cylindrical Algebraic Decomposition

KW - problem formulation

KW - heuristic

UR - http://dx.doi.org/10.1109/SYNASC.2014.15

UR - http://synasc.ro/2014/

U2 - 10.1109/SYNASC.2014.15

DO - 10.1109/SYNASC.2014.15

M3 - Conference contribution

SN - 978-1-4799-8447-3

SP - 53

EP - 60

BT - Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2014 16th International Symposium on

PB - IEEE

ER -