论文标题
计算不变代数系统的关键点
Computing critical points for invariant algebraic systems
论文作者
论文摘要
令$ \ mathbf {k} $为一个字段，$ ϕ $，$ \ mathbf {f} =（f_1，\ ldots，f_s）$ in $ \ mathbf {k} [x_1，\ dots，x_n] $ \ {1，\ dots，n \} $的排列组。我们考虑计算$ \ mathbf {f} $消失的点的问题和与$ \ mathbf {f}关联的jacobian矩阵，ϕ $是排名不足的，只要该集合是有限的。我们利用输入的不变性属性，根据$ \ Mathcal {s} _n $的轨道拆分解决方案空间。这使我们能够设计一种算法，该算法对解决方案空间进行了三角形描述，并在$ d^s $中进行多项式运行，$ {{n+d} \选择{d}} $和$ \ binom {n} {n} {s+1} {s+1} $，其中$ d $ where $ d $是输入polynomomials的最大程度。当$ d，s $固定时，这是$ n $的多项式，而当$ s $固定和$ d \ simeq n $时，这会导致相对于通常的多项式系统求解算法的指数加速。
Let $\mathbf{K}$ be a field and $ϕ$, $\mathbf{f} = (f_1, \ldots, f_s)$ in $\mathbf{K}[x_1, \dots, x_n]$ be multivariate polynomials (with $s < n$) invariant under the action of $\mathcal{S}_n$, the group of permutations of $\{1, \dots, n\}$. We consider the problem of computing the points at which $\mathbf{f}$ vanish and the Jacobian matrix associated to $\mathbf{f}, ϕ$ is rank deficient provided that this set is finite. We exploit the invariance properties of the input to split the solution space according to the orbits of $\mathcal{S}_n$. This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in $d^s$, ${{n+d}\choose{d}}$ and $\binom{n}{s+1}$ where $d$ is the maximum degree of the input polynomials. When $d,s$ are fixed, this is polynomial in $n$ while when $s$ is fixed and $d \simeq n$ this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.
