（半）代数系统的几何结构分析的高效算法及其应用

With the development of science and technology, the application of semi-algebraic sets becomes more and more important in scientific and engineering computation. Thus the requirements for the efficiency of the tools of analyzing semi-algebraic sets become higher than before and the requirements for the understanding of properties of the semi-algebraic sets becomes deeper than before. This project focuses on designing efficient algorithms to analyze the geometric structures (including the topology, geometric structure, Betti numbers, Euler-Poincare characteristic et al) and implementing the algorithms. Some applications related to semi-algebraic sets will be considered based on these algorithms.

随着科技的发展，半代数系统的应用在科学和工程计算中发挥着越来越重要的作用。从而对半代数系统结构分析的工具的效率要求越来越高，对研究的半代数集的一些基本属性了解的要求也越来越高。该项目将主要致力于研究分析半代数集几何结构（包括拓扑结构分析，几何结构分析，拓扑不变量（贝蒂数，欧拉示性数）的计算等）的高效算法并予以实现为主要目标。并以此为基础做一些相关的应用研究。

(半)代数系统的应用工程和科学计算中发挥着越来越重要的作用，比如机器人路径规划，机器人碰撞检测等。对半代数系统结构分析的工具的效率要求越来越高. 对研究的半代数集的一些基本属性了解的要求也越来越高。该项目主要目的是设计求解有限区域的高次方程组实根的高效算法并予以实现。并以此为基础做一些相关的应用研究。本项目目前已发表SCI期刊论文2篇，EI收录国际会议3篇，在审论文5篇（全部是SCI收录期刊或EI收录顶级会议），已完成在修改论文2篇。. 我们提出的纯符号方法可以求解100次的稠密双变元系统的实根。目前我们给出了数值隔离双变元系统实根的新方法，程序实现了非稠密的1000次的多项式系统的实根隔离。在实根求解上，我们提出的水平集方法求得20000次双变元系统的实根。. 我们提出多项式系统的根精炼方法比已有的方法规模小，效率高，在过约束系统的验证上提出了不同的方法。. 提出了空间代数曲线拓扑计算的新方法，首次不需要计算其一般位置，我们的算法复杂度也比已有的方法降低了N^6。. 提出了N维空间曲线的可信数值追踪方法，并程序实现，可用于可信的多项式方程求解的同伦方法中。