RUI: Practical Computing with Semi-Algebraic Sets via Cylindrical Algebraic Decomposition

United States Naval Academy- Do Not Use, Annapolis MD

Investigators

Abstract

PROPOSAL NUMBER: 0306440 INSTITUTION: United States Naval Academy PRINCIPAL INVESTIGATOR: Brown, Christopher W. PROPOSAL TITLE: RUI: Practical Computing with Semi-Algebraic Sets via Cylindrical Algebraic Decomposition ABSTRACT The purpose of this research is to develop algorithms and produce programs that are able to perform practical symbolic computations with semi-algebraic sets. The primary tool for this is Cylindrical Algebraic Decomposition (CAD), which provides a data-structure for explicitly representing semi-algebraic sets. CAD is a powerful and general tool, which has been implemented several times and already shown itself to be of more than just theoretical value. However, the consensus in the literature is that interesting application problems cannot be solved by current CAD programs within a reasonable amount of time and space. The three principal goals of the project are to extend the theory of CADs to deal efficiently with the types of semi-algebraic sets that arise in applications, produce efficient algorithms and programs that compute with CADs, and promote the use of CADs to solve problems in other disciplines. A wide variety of problems from many areas of science and engineering reduce to questions about semi-algebraic sets, that is sets containing both numeric and symbolic entities. Problems come, for example from control theory, robotics, computer-aided design, geometric theorem proving, and even epidemiology. There are many advantages to performing these computations symbolically, foremost among them is that free parameters in the problem description remain free parameters in the solution, so that a single computation provides solutions to whole families of problems. The primary disadvantage to computing symbolically with semi-algebraic sets is simple but profound: the time and space requirements are typically prohibitive. To be an effective tool for applications, symbolic methods for computing with semi-algebraic sets must be able to solve practical sized problems in a reasonable amount of time and space, which is precisely the goal towards which this project aims to contribute. Since this work focuses on practical computing with semi-algebraic sets, its theoretical improvements are incorporated into actual programs. Furthermore, these programs are freely and easily available (via the Web) to others to encourage experimentation with their use in science and engineering. Finally, the results of such experiments help direct further theoretical effort. Student participation is an integral part of this research.