论文标题
计算代数超出表面的真实隔离点
Computing the Real Isolated Points of an Algebraic Hypersurface
论文作者
论文摘要
令$ \ mathbb {r} $为实数的字段。我们考虑计算$ \ mathbb {r}^n $中真实代数集的真实隔离点的问题，作为多项式系统的消失集。这个问题对于研究材料设计中机制的刚性特性起着重要作用。在本文中，我们设计了一种解决此问题的算法。它基于关键点的计算以及在实际代数集中回答连接查询的路线图。这导致了一种复杂性$（nd）^{o（n \ log（n））} $的概率算法，用于计算$ d $的真实代数超出图的真实隔离点。它使我们能够在实践实例中求解，这些实例无法实现最先进的情况。
Let $\mathbb{R}$ be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in $\mathbb{R}^n$ given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of mechanism in material designs. In this paper, we design an algorithm which solves this problem. It is based on the computations of critical points as well as roadmaps for answering connectivity queries in real algebraic sets. This leads to a probabilistic algorithm of complexity $(nd)^{O(n\log(n))}$ for computing the real isolated points of real algebraic hypersurfaces of degree $d$. It allows us to solve in practice instances which are out of reach of the state-of-the-art.
