Loading...
Please wait, while we are loading the content...
A Parallel Cylindrical Algebraic Decomposition Algorithm for Quantifier Elimination on Real Closed Fields
| Content Provider | CiteSeerX |
|---|---|
| Author | Malladi, Hari Krishna Dukkipati, Ambedkar |
| Abstract | In this paper we propose a parallel approach to quantifier elimination on real closed fields through a modification in the cylindrical algebraic decomposition (CAD) algorithm to accommodate parallelism. In this approach the speed-up due to parallelism obtained on an input formula is a prop-erty of that formula itself. Hence the time complexity of algorithm depends on not just the size of the input but on the input self. We classify prenex formulae depending on the amount of input-based parallelism that can be obtained from it based on which we obtain some insights into the complexity of the algorithm. We demonstrate performance of the proposed algorithm with experimental results. |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
