权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Cylindrical Algebraic Decomposition

圆柱代数分解

基本信息

批准号：
1940105
负责人：
金额：
--
依托单位：
University of Bath
依托单位国家：
英国
项目类别：
Studentship
财政年份：
2017
资助国家：
英国
起止时间：
2017 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=studentship-1940105
关键词：
Cylindrical Algebraic Decomposition

项目摘要

Cylindrical Algebraic Decomposition is a general-purpose computation technique underpinning many questions inreal algebraic geometry and its applications,e.g. robot motion planning. There are various algorithms for producing such decompositions. However, all knownalgorithms produce objects which,while Cylindrical Algebraic Decompositions, also satisfy certain other properties. These are generally not wellarticulated,and we would like to makethis precise. Many issues, such as adjacency, are currently not solved for Cylindrical Algebraic Decompositions,because of the generality of the definition.We suspect that having a more precise description of the sort of decompositions produced in practice would make iteasier to produce algorithms that are veryuseful in applications. The Bath group have made many developments in CAD based on McCallum's projection as atool for constructing such CADs. But McCallum'sprojection can fail. Recently McCallum and colleagues have proved that a different projection (Lazard's), andassociated different lifting algorithms, never fails.The starting phase of the project revolves around gathering background information regarding CAD, specificallyaround McCallum's and Lazard's projection. During this phase I willbe attending the computer algebra course offered to third years in the computer science department as this coversthe basics of CAD. Apart from CAD I will be broadening myknowledge in Algebraic Geometry, as required by the scope of the project, and will be attending the regular geometryseminars that are held at the University of Bath.As a starting point I will be focussing my attention towards understanding the piano mover's problem, which askswhether, given an object and its configuration space,it is possible to move the object from point A to point B. If this is possible what is the most efficient way to do so?

圆柱代数分解是一种通用的计算技术，它支持实代数几何中的许多问题及其应用，例如机器人运动规划。存在用于产生这样的分解的各种算法。然而，所有已知的算法产生的对象，而圆柱代数分解，也满足某些其他属性。这些通常不是很精确的，我们想使之精确。许多问题，如邻接，目前还没有解决圆柱代数分解，因为定义的一般性，我们怀疑，有一个更精确的描述，在实践中产生的分解类将使迭代更容易产生算法，是非常有用的应用。Bath小组在McCallum投影的基础上对CAD进行了许多开发，作为构建此类CAD的工具。但麦卡勒姆的预测可能会失败。最近McCallum和他的同事们证明了一种不同的投影（Lazard的），以及相关的不同的提升算法，永远不会失败。该项目的开始阶段围绕着收集有关CAD的背景信息，特别是围绕McCallum和Lazard的投影。在这个阶段，我将参加计算机科学系三年级的计算机代数课程，因为这涵盖了CAD的基础知识。除了计算机辅助设计，我将扩大我的知识在代数几何，所需的范围内的项目，并将参加定期geometryseminars是在巴斯大学举行。作为一个起点，我将集中我的注意力对理解钢琴移动的问题，which asks是否，给定一个对象和它的配置空间，它是可能的移动对象从点A到点B。如果可以的话，最有效的方法是什么？