圆柱代数分解的几何方法

A Geometric Approach to Cylindrical Algebraic Decomposition

摘要 Abstract

圆柱代数分解是实代数几何中的经典构造。尽管已有多种算法可以计算圆柱代数分解,但其实际性能仍然非常有限。本文从更几何的角度重新审视了该问题,将圆柱代数分解的构造与实簇之间的态射研究联系起来。结果表明,几何纤维的基数(几何属性)决定了半代数连续截面(半代数属性)的存在性。由此,在投影阶段可以系统地利用所有方程,从而得到一个新且简单的算法,其实验结果证明了其效率。

Cylindrical algebraic decomposition is a classical construction in real algebraic geometry. Although there are many algorithms to compute a cylindrical algebraic decomposition, their practical performance is still very limited. In this paper, we revisit this problem from a more geometric perspective, where the construction of cylindrical algebraic decomposition is related to the study of morphisms between real varieties. It is showed that the geometric fiber cardinality (geometric property) decides the existence of semi-algebraic continuous sections (semi-algebraic property). As a result, all equations can be systematically exploited in the projection phase, leading to a new simple algorithm whose efficiency is demonstrated by experimental results.