On the bit complexity of polynomial system solving
| Autor: | Guillermo Matera, Nardo Giménez |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Statistics and Probability
Rational number Polynomial Control and Optimization General Mathematics Modulo LUCKY PRIMES Prime (order theory) Reduction (complexity) purl.org/becyt/ford/1 [https] POLYNOMIAL SYSTEM SOLVING OVER Q ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION CHOW FORM Computer Science::Distributed Parallel and Cluster Computing Mathematics Discrete mathematics Numerical Analysis Algebra and Number Theory Applied Mathematics Prime number Astrophysics::Instrumentation and Methods for Astrophysics purl.org/becyt/ford/1.1 [https] Randomized algorithm Hypersurface LIFTING FIBERS BIT COMPLEXITY REDUCED REGULAR SEQUENCE |
| Zdroj: | CONICET Digital (CONICET) Consejo Nacional de Investigaciones Científicas y Técnicas instacron:CONICET |
| Popis: | We describe and analyze a randomized algorithm which solves a polynomial system over the rationals defined by a reduced regular sequence outside a given hypersurface. We show that its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size. The algorithm solves the input system modulo a prime number p and applies p-adic lifting. For this purpose, we establish a number of results on the bit length of a “lucky” prime p, namely one for which the reduction of the input system modulo p preserves certain fundamental geometric and algebraic properties of the original system. These results rely on the analysis of Chow forms associated to the set of solutions of the input system and effective arithmetic Nullstellensätze. Fil: Gimenez, Nardo Ariel. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina Fil: Matera, Guillermo. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|