论文标题
通过Hermite矩阵求解多项式方程的参数系统
Solving parametric systems of polynomial equations over the reals through Hermite matrices
论文作者
论文摘要
我们设计了一种用于求解参数系统的新算法，该系统具有有限的许多复杂解决方案，用于参数的通用值。更准确地说，令$ f =（f_1，\ ldots，f_m）\ subset \ subset \ mathbb {q} [y] [x] $，$ y =（y_1，\ ldots，y_t）$ and $ x =（x_1，x_1，x_1，\ ldots，\ ldots，x_n）$，$ v \ subset be be n e an be be be be be be be be n e an e an be be be设置由$ f $和$π$定义为投影$（y，x）\ to y $。在假设$ f $以$ y $的通用值中有限的许多复杂根，而由$ f $产生的理想是激进的，我们解决了以下问题。在输入$ f $上，我们计算定义半代数的半代数公式$ s_1，\ ldots，$ y $ -space的s_l $，以至于$ \ cup_ {i = 1}^l s_i $ in $ \ s_i $ in $ \ nathbb {r}当$η$在每个$ s_i $上都变化时，是不变的。 该算法利用了代数$ \ mathbb {q}（y）[x]/i $ $ i $在$ \ mathbb {q}（q}（y）[x] $中生成的理想生成的理想，$ i $是$ f $生成的理想，$ i $的理想生成的理想物质和所谓的Hermite Ermite Matite Matite MatiTrices的专业属性。这使我们能够通过编码对称矩阵的签名的半代数公式来获得集合$ s_i $的紧凑表示形式。当$ f $满足额外的通用假设时，我们会在$ \ mathbb {q} $和输出多项式的程度上获得算术操作数量的复杂性界限。令$ d $是$ f_i $'s和$ d = n（d-1）d^n $的最大程度d^{3nt+2（n+t）+1}）$在$ \ mathbb {q} $中操作，并且所涉及的多项式的学位为$ d $。 我们报告实验的实际实验，这些实验说明了我们算法对应用程序和系统的效率。它使我们能够解决无法解决的问题。
We design a new algorithm for solving parametric systems having finitely many complex solutions for generic values of the parameters. More precisely, let $f = (f_1, \ldots, f_m)\subset \mathbb{Q}[y][x]$ with $y = (y_1, \ldots, y_t)$ and $x = (x_1, \ldots, x_n)$, $V\subset \mathbb{C}^{t+n}$ be the algebraic set defined by $f$ and $π$ be the projection $(y, x) \to y$. Under the assumptions that $f$ admits finitely many complex roots for generic values of $y$ and that the ideal generated by $f$ is radical, we solve the following problem. On input $f$, we compute semi-algebraic formulas defining semi-algebraic subsets $S_1, \ldots, S_l$ of the $y$-space such that $\cup_{i=1}^l S_i$ is dense in $\mathbb{R}^t$ and the number of real points in $V\cap π^{-1}(η)$ is invariant when $η$ varies over each $S_i$. This algorithm exploits properties of some well chosen monomial bases in the algebra $\mathbb{Q}(y)[x]/I$ where $I$ is the ideal generated by $f$ in $\mathbb{Q}(y)[x]$ and the specialization property of the so-called Hermite matrices. This allows us to obtain compact representations of the sets $S_i$ by means of semi-algebraic formulas encoding the signature of a symmetric matrix. When $f$ satisfies extra genericity assumptions, we derive complexity bounds on the number of arithmetic operations in $\mathbb{Q}$ and the degree of the output polynomials. Let $d$ be the maximal degree of the $f_i$'s and $D = n(d-1)d^n$, we prove that, on a generic $f=(f_1,\ldots,f_n)$, one can compute those semi-algebraic formulas with $O^~( \binom{t+D}{t}2^{3t}n^{2t+1} d^{3nt+2(n+t)+1})$ operations in $\mathbb{Q}$ and that the polynomials involved have degree bounded by $D$. We report on practical experiments which illustrate the efficiency of our algorithm on generic systems and systems from applications. It allows us to solve problems which are out of reach of the state-of-the-art.
