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

提案编号：0306440机构：美国海军学院主要研究者：布朗，克里斯托弗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.