Real Geometry and Connectedness - A survey of Cylindrical Algebraic Decomposition

David Wilson

(University of Bath)

Since its introduction in 1975, cylindrical algebraic decomposition (CAD) has proven a useful practical tool for quantifi er elimination over real-closed fields. Despite a doubly exponential complexity in the number of variables, it has seen applications in other areas of computer algebra (such as Branch Cut Analysis) and Robot Motion Planning. A history of various developments will be given before discussing recent research work by the research team in Bath - including preconditioning with Gröbner Bases and Truth Table Invariant CADs. Finally, future research directions will be sketched out.
Thursday 6th December 2012, 14:00
Far-134 (Video Conferencing Room)
Department of Computer Science