HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces

Abstract : The condition-based complexity analysis framework is one of the gems of modern numerical algebraic geometry and theoretical computer science. One of 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. We demonstrate its capabilities by providing a new probabilistic complexity analysis for the Plantinga-Vegter algorithm, which covers both random sparse (alas a restricted sparseness structure) polynomials and random Gaussian polynomials. We present explicit results with structured random polynomials for problems with two or more dimensions. Additionally, we provide some estimates of the separation bound of a univariate polynomial in our current framework.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

Contributor : Josué Tonelli-Cueto Connect in order to contact the contributor
Submitted on : Monday, June 8, 2020 - 10:54:47 AM
Last modification on : Thursday, April 7, 2022 - 1:58:24 PM



Josué Tonelli-Cueto, Elias Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces. Proceedings of the 2020 International Symposium on Symbolic and Algebraic Computation, ISSAC'20, Jul 2020, Kalamata, Greece. pp.434-441, ⟨10.1145/3373207.3404054⟩. ⟨hal-02736942v2⟩



Record views


Files downloads