### Abstract

Original language | English |
---|---|

Title of host publication | Intelligent Computer Mathematics |

Subtitle of host publication | MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings |

Editors | Jacques Carette, David Aspinall, Christoph Lange, Petr Sojka, Wolfgang Windsteiger |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 19-34 |

Number of pages | 15 |

ISBN (Electronic) | 9783642393204 |

ISBN (Print) | 9783642393198 |

DOIs | |

Publication status | Published - 2013 |

Event | Conferences on Intelligent Computer Mathematics: CICM 2013 - Bath, UK United Kingdom Duration: 7 Jul 2013 → 11 Jul 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 7961 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | Conferences on Intelligent Computer Mathematics: CICM 2013 |
---|---|

Country | UK United Kingdom |

City | Bath |

Period | 7/07/13 → 11/07/13 |

### Fingerprint

### Keywords

- cylindrical algebraic decomposition
- Groebner bases
- problem formulation
- symbolic computation
- equational constraint

### Cite this

*Intelligent Computer Mathematics: MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings*(pp. 19-34). (Lecture Notes in Computer Science; Vol. 7961). Berlin: Springer. https://doi.org/10.1007/978-3-642-39320-4_2

**Optimising problem formulation for cylindrical algebraic decomposition.** / Bradford, Russell; Davenport, James H; England, Matthew; Wilson, David.

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

*Intelligent Computer Mathematics: MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings.*Lecture Notes in Computer Science, vol. 7961, Springer, Berlin, pp. 19-34, Conferences on Intelligent Computer Mathematics: CICM 2013, Bath, UK United Kingdom, 7/07/13. https://doi.org/10.1007/978-3-642-39320-4_2

}

TY - GEN

T1 - Optimising problem formulation for cylindrical algebraic decomposition

AU - Bradford, Russell

AU - Davenport, James H

AU - England, Matthew

AU - Wilson, David

PY - 2013

Y1 - 2013

N2 - Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing the variable ordering for a CAD problem, choosing a designated equational constraint and choosing clause formulation for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

AB - Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing the variable ordering for a CAD problem, choosing a designated equational constraint and choosing clause formulation for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

KW - cylindrical algebraic decomposition

KW - Groebner bases

KW - problem formulation

KW - symbolic computation

KW - equational constraint

UR - http://www.scopus.com/inward/record.url?scp=84880711618&partnerID=8YFLogxK

UR - http://www.cicm-conference.org/2013/

UR - http://dx.doi.org/10.1007/978-3-642-39320-4_2

U2 - 10.1007/978-3-642-39320-4_2

DO - 10.1007/978-3-642-39320-4_2

M3 - Conference contribution

SN - 9783642393198

T3 - Lecture Notes in Computer Science

SP - 19

EP - 34

BT - Intelligent Computer Mathematics

A2 - Carette, Jacques

A2 - Aspinall, David

A2 - Lange, Christoph

A2 - Sojka, Petr

A2 - Windsteiger, Wolfgang

PB - Springer

CY - Berlin

ER -