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

建议编号：0306440 INSTITUTION：美国海军研究院PRINCIPAL研究员：Brown，Christopher W.PROPOSAL标题：RUI：基于柱代数分解的半代数集的实用计算本研究的目的是开发能够使用半代数集进行实际符号计算的算法和程序。这方面的主要工具是柱面代数分解(CAD)，它为显式表示半代数集提供了一种数据结构。CAD是一个强大而通用的工具，它已经被实施了几次，并且已经证明自己不仅仅是理论上的价值。然而，文献中的共识是，有趣的应用问题不能通过现有的CAD程序在合理的时间和空间内解决。该项目的三个主要目标是扩展CADS理论以有效地处理应用中出现的半代数集的类型，产生用CADS计算的高效算法和程序，并促进使用CADS来解决其他学科中的问题。来自许多科学和工程领域的各种问题归结为关于半代数集的问题，即包含数字和符号实体的集合。例如，问题来自控制理论、机器人学、计算机辅助设计、几何定理证明，甚至是流行病学。象征性地执行这些计算有许多优点，其中最重要的是问题描述中的自由参数在解中保持自由参数，这样一次计算就可以为整个问题族提供解决方案。使用半代数集进行符号计算的主要缺点是简单但深刻的：时间和空间要求通常是令人望而却步的。为了成为一种有效的应用工具，使用半代数集进行计算的符号方法必须能够在合理的时间和空间内解决实际规模的问题，这正是本项目致力于实现的目标。由于这项工作侧重于使用半代数集进行实际计算，因此其理论改进被结合到实际程序中。此外，这些程序对其他人来说是免费和容易的(通过Web)，以鼓励在科学和工程中使用它们进行实验。最后，这些实验的结果有助于指导进一步的理论工作。学生参与是这项研究不可或缺的一部分。

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.