论文标题
立方体的条件号。 I：单变量多项式和超曲面
Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces
论文作者
论文摘要
基于条件的复杂性分析框架是现代数值代数几何和理论计算机科学的宝石之一。它提出的挑战之一是扩大我们可以处理的当前有限的随机多项式范围。尽管最近有了重要的进展，但可用的工具仍无法处理随机的稀疏多项式和高斯多项式，即多项式的系数为i.i.d。高斯随机变量。 我们基于基于立方的规范来启动基于条件的复杂性框架，这是朝这个方向迈出的一步。我们为真实的超曲面和单变量多项式提供了此框架。我们在非常温和的概率假设下证明了它在两个问题中的能力。一方面，我们表明，对于随机稀疏（a listiver a的稀疏结构）多项式和随机的高斯多项式，种植算法的平均运行时间在该程度上是多项式的。另一方面，我们研究了Jindal和Sagraloff（Arxiv：1704.06979）的笛卡尔求解器和求解器的运行时间的细分树的大小。在这两种情况下，我们都提供了一个在输入尺寸（支撑的大小以及度对数的大小）中，不仅为平均值，而且在所有较高的矩中。
The condition-based complexity analysis framework is one of the gems of modern numerical algebraic geometry and theoretical computer science. Among the challenges that it poses is to expand the currently limited range of random polynomials that we can handle. Despite important recent progress, the available tools cannot handle random sparse polynomials and Gaussian polynomials, that is polynomials whose coefficients are i.i.d. Gaussian random variables. We initiate a condition-based complexity framework based on the norm of the cube that is a step in this direction. We present this framework for real hypersurfaces and univariate polynomials. We demonstrate its capabilities in two problems, under very mild probabilistic assumptions. On the one hand, we show that the average run-time of the Plantinga-Vegter algorithm is polynomial in the degree for random sparse (alas a restricted sparseness structure) polynomials and random Gaussian polynomials. On the other hand, we study the size of the subdivision tree for Descartes' solver and run-time of the solver by Jindal and Sagraloff (arXiv:1704.06979). In both cases, we provide a bound that is polynomial in the size of the input (size of the support plus the logarithm of the degree) not only for the average but also for all higher moments.
