Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
| Autor: | Pierre Lairez |
|---|---|
| Přispěvatelé: | Symbolic Special Functions : Fast and Certified (SPECFUN), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] General Mathematics Gaussian 010103 numerical & computational mathematics Computational Complexity (cs.CC) 01 natural sciences Combinatorics Continuation symbols.namesake Line segment FOS: Mathematics Mathematics - Numerical Analysis 0101 mathematics Condition number Mathematics Polynomial (hyperelastic model) Degree (graph theory) Applied Mathematics Linear space 010102 general mathematics Numerical Analysis (math.NA) [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA] Computer Science - Computational Complexity Numerical continuation 68Q25 (Primary) 65H10 65H20 65Y20 (Secondary) symbols |
| Zdroj: | Journal of the American Mathematical Society Journal of the American Mathematical Society, In press, 33 (2), pp.487-526. ⟨10.1090/jams/938⟩ Journal of the American Mathematical Society, American Mathematical Society, In press, 33 (2), pp.487-526. ⟨10.1090/jams/938⟩ |
| ISSN: | 0894-0347 |
| DOI: | 10.1090/jams/938⟩ |
| Popis: | How many operations do we need on average to compute an approximate root of a random Gaussian polynomial system? Beyond Smale’s 17th problem that asked whether a polynomial bound is possible, we prove a quasi-optimal bound (input size) 1 + o ( 1 ) \text {(input size)}^{1+o(1)} . This improves upon the previously known (input size) 3 2 + o ( 1 ) \text {(input size)}^{\frac 32 +o(1)} bound. The new algorithm relies on numerical continuation along rigid continuation paths. The central idea is to consider rigid motions of the equations rather than line segments in the linear space of all polynomial systems. This leads to a better average condition number and allows for bigger steps. We show that on average, we can compute one approximate root of a random Gaussian polynomial system of n n equations of degree at most D D in n + 1 n+1 homogeneous variables with O ( n 4 D 2 ) O(n^4 D^2) continuation steps. This is a decisive improvement over previous bounds that prove no better than 2 min ( n , D ) \sqrt {2}^{\min (n, D)} continuation steps on average. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|