参数半代数系统的误差可控计算理论与算法

Parametric semi-algebraic systems are systems consisting of polynomial equation and inequality constraints with parametric coefficients. Such systems appear widely in robot control, formal verification of hybrid systems, stability analysis of biological systems, computer program verification and optimization, etc. The core of solving parametric semi-algebraic systems is to find a partition of the parameter space such that the topological and geometrical properties of the solutions remain invariant in the same cell. Currently, the main tools for solving parametric semi-algebraic systems are based on symbolic computation. In this project, we will explore the theory of numerically generating connected open cells from finitely many points to overcome the expression swell problem occurring in cylindrical algebraic decomposition and other symbolic methods. To handle the problem of numerical instability caused by factors such as multiple roots and sum of squares, we will explore the full rank representation of semi-algebraic sets based on hybrid real triangular decomposition methods. Through the implementation of this project, we will develop error controllable and structure oriented methods for efficiently computing the critical points of a polynomial map on a semi-algebraic set, stable numerical methods for computing the connected path map of semi-algebraic sets, as well as efficient online connected components identification and real homotopy construction. Based on these techniques, we will establish error controllable computation theory and methods for completely describing the topological and geometrical structure of the solution sets of a parametric system for parameter values not close to lower dimensional boundaries. The methods proposed in this project is expected to be widely applied to stability analysis, formal verification and other related fields.

参数半代数系统是一类由含参系数的多项式等式和不等式约束构成的系统，其在机器人控制、混成系统形式化验证、生物系统稳定性分析、计算机程序验证和优化等应用中广泛存在，求解参数半代数系统的核心是找到参数空间的划分使得同一胞腔内解的拓扑和几何性质不变。目前参数半代数系统求解主要依赖于符号计算。本项目将探索连通开胞腔的数值有限点集生成理论，克服柱形代数分解等方法的表达式膨胀难题；探索基于混合实三角分解的半代数集满秩表示，解决重根、平方和等因素引起的数值不稳定问题。通过本项目的实施，我们将发展误差可控和结构导向的半代数集多项式映射下的临界点集高效计算、数值稳定的半代数集连通路径图计算以及高效的在线连通分支识别和实同伦构造方法，建立起能够完整刻画参数系统远离低维边界的解的拓扑和几何结构的误差可控计算理论和方法。本项目提出的方法有望广泛应用于稳定性分析、形式化验证等相关应用领域。

参数半代数系统的求解是计算实代数几何的主要研究对象之一，在生物系统稳定性分析、程序验证、控制系统分析等诸多领域都有应用，其核心研究问题是发现参数和系统实数解之间的变化关系。围绕这一课题，我们从理论、算法、应用和高效实现等方面开展了一系列的研究和探索，重点研究了以下几方面的内容：1）高维空间实代数簇连通分支样本点以及实代数曲线和曲面的误差可控计算和表示；2）带结构的参数半代数系统的高效误差可控算法；3）参数半代数系统算法的高效实现及应用。 理论和算法方面，我们完整建立了双参数半代数系统误差可控计算的理论并给出了多参数情况下的计算框架，针对生物系统稳定分析等应用中出现的结构对算法进行了优化，将参数半代数系统的求解规模从几变元扩展到20个变元左右。作为这一工作的基础，我们提出了实代数簇满秩分解的概念和符号数值混合的计算方法；提出了基于罚函数的计算奇异实代数簇连通分支样本点的方法；给出了定义系统几乎处处满秩和完全亏秩两种情况下不同的误差可控的高维空间代数曲线绘制方法；提出了数值连通路径图的概念、理论和算法用于实代数曲面的表示。我们厘清了零误差计算的基础，即从一个实数的近似值恢复出其准确值的前提是这个数属于某个一致离散集合；解决了误差干扰情况下恢复实代数数的PSLQ算法的终止性、正确性和稳定性问题。应用方面，我们融合半代数系统的符号数值计算和机器学习方法，在量子关联高效判定、控制系统分析、循环程序终止性等问题中取得新突破。高效实现方面，我们开发并发布了实代数曲线绘制包ApproxPlot, 参数半代数系统求解和生物系统稳定点分析软件包GeoBlock，将用于半代数系统精确求解的柱形代数分解和实量词消去模块集成进计算机代数系统Maple中；实现了保变元稀疏性的多项式系统渐增三角分解算法; 通过对循环分块空间探索的优化加速了矩阵乘法等基本运算的效率。