### Abstract

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

Title of host publication | Computer Algebra in Scientific Computing |

Subtitle of host publication | Proceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014 |

Editors | V. P. Gerdt, W. Koepf, W. M. Seiler, E. V. Vorozhtsov |

Publisher | Springer |

Pages | 44-58 |

Number of pages | 15 |

Volume | 8660 |

ISBN (Print) | 9783319105147 |

DOIs | |

Publication status | Published - 2014 |

### Publication series

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

Publisher | Springer |

### Fingerprint

### Keywords

- cylindrical algebraic decomposition
- equational constraint
- regular chains
- triangular decomposition

### Cite this

*Computer Algebra in Scientific Computing: Proceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014*(Vol. 8660, pp. 44-58). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-319-10515-4_4

**Truth table invariant cylindrical algebraic decomposition by regular chains.** / Bradford, Russell; Chen, Changbo; Davenport, James H.; England, Matthew; Moreno Maza, Marc; Wilson, David.

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

*Computer Algebra in Scientific Computing: Proceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014.*vol. 8660, Lecture Notes in Computer Science, Springer, pp. 44-58. https://doi.org/10.1007/978-3-319-10515-4_4

}

TY - CHAP

T1 - Truth table invariant cylindrical algebraic decomposition by regular chains

AU - Bradford, Russell

AU - Chen, Changbo

AU - Davenport, James H.

AU - England, Matthew

AU - Moreno Maza, Marc

AU - Wilson, David

PY - 2014

Y1 - 2014

N2 - A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is truth table invariant (a TTICAD) meaning given formulae have constant truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.

AB - A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is truth table invariant (a TTICAD) meaning given formulae have constant truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.

KW - cylindrical algebraic decomposition

KW - equational constraint

KW - regular chains

KW - triangular decomposition

UR - http://arxiv.org/abs/1401.6310

UR - http://www14.in.tum.de/CASC2014/

UR - http://dx.doi.org/10.1007/978-3-319-10515-4_4

U2 - 10.1007/978-3-319-10515-4_4

DO - 10.1007/978-3-319-10515-4_4

M3 - Chapter

SN - 9783319105147

VL - 8660

T3 - Lecture Notes in Computer Science

SP - 44

EP - 58

BT - Computer Algebra in Scientific Computing

A2 - Gerdt, V. P.

A2 - Koepf, W.

A2 - Seiler, W. M.

A2 - Vorozhtsov, E. V.

PB - Springer

ER -