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

提案编号：0306440机构：美国海军学院首席研究员：Brown， Christopher w .提案标题：RUI：通过柱代数分解的半代数集的实用计算摘要本研究的目的是开发算法并生成能够使用半代数集进行实用符号计算的程序。这方面的主要工具是圆柱代数分解（CAD），它为显式表示半代数集提供了一种数据结构。CAD是一个强大而通用的工具，它已经被实现了几次，并且已经显示出它的不仅仅是理论价值。然而，文献中的共识是，当前的CAD程序无法在合理的时间和空间内解决有趣的应用问题。该项目的三个主要目标是扩展cad的理论，以有效地处理应用中出现的半代数集的类型，产生有效的算法和使用cad计算的程序，并促进使用cad来解决其他学科的问题。许多科学和工程领域的各种各样的问题都可以归结为半代数集的问题，即包含数字和符号实体的集合。例如，问题来自控制论、机器人、计算机辅助设计、几何定理证明，甚至流行病学。以符号方式进行这些计算有许多优点，其中最重要的是问题描述中的自由参数仍然是解中的自由参数，因此一次计算就可以为整个问题族提供解。用半代数集进行符号化计算的主要缺点很简单，但却很严重：时间和空间要求通常令人望而却步。为了成为一种有效的应用工具，用于半代数集计算的符号方法必须能够在合理的时间和空间内解决实际规模的问题，这正是本项目旨在贡献的目标。由于这项工作侧重于半代数集的实际计算，其理论改进被纳入实际程序。此外，这些程序是免费和容易获得的（通过网络），以鼓励他们在科学和工程中使用的实验。最后，这些实验的结果有助于指导进一步的理论工作。学生的参与是这项研究不可分割的一部分。

PROPOSAL NUMBER: 0306440INSTITUTION: United States Naval AcademyPRINCIPAL INVESTIGATOR: Brown, Christopher W.PROPOSAL TITLE: RUI: Practical Computing with Semi-Algebraic Sets via Cylindrical Algebraic DecompositionABSTRACTThe 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.