Abstract | ||
---|---|---|
We derive efficient algorithms for coarse approximation of complex algebraic hypersurfaces, useful for estimating the distance between an input polynomial zero set and a given query point. Our methods work best on sparse polynomials of high degree (in any number of variables) but are nevertheless completely general. The underlying ideas, which we take the time to describe without an excess of algebraic geometry terminology, come from tropical geometry. We then apply our methods to finding roots of n × n systems near a given query point, thereby reducing a hard algebraic problem to high-precision linear optimization. We prove new upper and lower complexity estimates along the way. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-662-44900-4_15 | Mathematics and Visualization |
Field | DocType | Volume |
Discrete mathematics,Topology,Algebraic number,Amoeba (mathematics),Polynomial,Tropical geometry,Zero set,Linear programming,Time complexity,Mathematics | Journal | abs/1312.6547 |
ISSN | Citations | PageRank |
1612-3786 | 0 | 0.34 |
References | Authors | |
23 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Eleanor Anthony | 1 | 0 | 0.34 |
Sheridan Grant | 2 | 0 | 0.34 |
Peter Gritzmann | 3 | 412 | 46.93 |
J. Maurice Rojas | 4 | 194 | 34.26 |