Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Distributed-Memory Algorithm for Connected Components Labeling of Simulation Data Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Polynomial-Time Amoeba Neighborhood Membership and Faster Localized Solving

verfasst von : Eleanor Anthony, Sheridan Grant, Peter Gritzmann, J. Maurice Rojas

Erschienen in: Topological and Statistical Methods for Complex Data

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Realization of Regular Maps of Large Genus
Nächstes Kapitel Slycat Ensemble Analysis of Electrical Circuit Simulations
Fußnoten
1
A hole of a subset \(S\! \subseteq \! \mathbb{R}^{n}\) is simply a bounded connected component of the complement \(\mathbb{R}^{n}\setminus S\).
 
2
That is, smallest convex set containing…
 
3
The cell looks hexagonal because it has a pair of vertices too close to distinguish visually.
 
Literatur
1.
D’Andrea, C., Krick, T., Sombra, M.: Heights of varieties in multiprojective spaces and arithmetic Nullstellensatze. Ann. Sci. l’ENS fascicule 4, 549–627 (2013)MathSciNet
2.
D’Andrea, C., Galligo, A., Sombra, M.: Quantitative equidistribution for the solution of a system of sparse polynomial equations. Am. J. Math (to appear)
3.
Arora, S., Barak, B.: Computational Complexity. A Modern Approach. Cambridge University Press, Cambridge (2009)CrossRefMATH
4.
Avendaño, M., Kogan, R., Nisse, M., Rojas, J.M.: Metric Estimates and membership complexity for archimedean amoebae and tropical hypersurfaces. Submitted for publication, also available as Math ArXiV preprint 1307.3681
5.
Baker, A.: The theory of linear forms in logarithms. In: Transcendence Theory: Advances and Applications: Proceedings of a Conference Held at the University of Cambridge, Cambridge, January–February 1976. Academic, London (1977)
6.
Baker, M., Rumely, R.: Potential Theory and Dynamics on the Berkovich Projective Line. Mathematical Surveys and Monographs, vol. 159. American Mathematical Society, Providence (2010)
7.
Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Numerically Solving Polynomial Systems with Bertini. Software, Environments and Tools Series. Society for Industrial and Applied Mathematics (2013)
8.
Beltrán, C., Pardo, L.M.: Smale’s 17th problem: Average polynomial time to compute affine and projective solutions. J. Am. Math. Soc. 22, 363–385 (2009)CrossRefMATH
9.
10.
Bettale, L., Faugére, J.-C., Perret, L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Designs Codes Cryptogr. 69(1), 1–52 (2013)CrossRefMATH
11.
Bihan, F., Rojas, J.M., Stella, C.: Faster real feasibility via circuit discriminants. In: Proceedings of ISSAC 2009 (July 28–31, Seoul, Korea), pp. 39–46. ACM (2009)
12.
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer (1998)
13.
Bürgisser, P., Scheiblechner, P.: On the complexity of counting components of algebraic varieties. J. Symb. Comput. 44(9), 1114–1136 (2009)CrossRefMATH
14.
Bürgisser, P., Cucker, F.: Solving polynomial equations in smoothed polynomial time and a near solution to Smale’s 17th problem. In: Proceedings STOC (Symposium on the Theory of Computation) 2010, pp. 503–512. ACM (2010)
15.
De Loera, J.A., Rambau, J., Santos, F.: Triangulations, Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25. Springer, Berlin (2010)
16.
17.
Einsiedler, M., Kapranov, M., Lind, D.: Non-Archimedean amoebas and tropical varieties. J. die reine Angew. Math. (Crelles J.) 2006(601), 139–157 (2006)
18.
Emiris, I.Z., Canny, J.: Efficient incremental algorithms for the sparse resultant and mixed volume. J. Symb. Comput. 20(2), 117–149 (1995)CrossRefMATHMathSciNet
19.
Faugère, J.-C., Gaudry, P., Huot, L., Renault, G.: Using symmetries in the index calculus for elliptic curves discrete logarithm. J. Cryptol. 1–40 (2013)
20.
Faugère, J.-C., Hering, M., Phan, J.: The membrane inclusions curvature equations. Adv. Appl. Math. 31(4), 643–658 (2003).CrossRefMATH
21.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco (1979)MATH
22.
Gel’fand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston (1994)
23.
Gritzmann, P.: Grundlagen der Mathematischen Optimierung: Diskrete Strukturen, Komplexitätstheorie, Konvexitätstheorie, Lineare Optimierung, Simplex-Algorithmus, Dualität. Springer (2013)CrossRef
24.
Gritzmann, P., Klee, V.: On the complexity of some basic problems in computational convexity: I. Containment problems. Discrete Math. 136, 129–174 (1994)CrossRefMATHMathSciNet
25.
Gritzmann, P., Klee, V.: On the complexity of some basic problems in computational convexity: II. Volume and mixed volumes. In: Bisztriczky, T., McMullen, P., Schneider, R., Ivic Weiss A. (eds) Polytopes: Abstract, Convex and Computational, pp. 373–466. Kluwer, Boston (1994)
26.
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1993)CrossRefMATH
27.
Grünbaum, B.: Convex Polytopes. Wiley-Interscience, London (1967); Ziegler, G. (ed) Convex Polytopes, 2nd edn. Graduate Texts in Mathematics, vol. 221. Springer (2003)
28.
Hao, W., Hauenstein, J.D., Hu, B., Liu, Y., Sommese, A., Zhang, Y.-T.: Continuation along bifurcation branches for a tumor model with a necrotic core. J. Sci. Comput. 53, 395–413 (2012)CrossRefMATHMathSciNet
29.
Hauenstein, J., Rodriguez, J., Sturmfels, B.: Maximum likelihood for matrices with rank constraints. J. Algebraic Stat. 5(1), 18–38 (2014). Also available as Math ArXiV preprint 1210.0198
30.
Herbst, M., Hori, K., Page, D.: Phases of N​ = ​ 2 theories in 1 + 1 dimensions with boundary. High Energy Phys. ArXiV preprint 0803.2045v1
31.
Huan, L.J., Li, T.-Y.: Parallel homotopy algorithm for symmetric large sparse eigenproblems. J. Comput. Appl. Math. 60(1–2), 77–100 (1995)CrossRefMathSciNet
32.
Itenberg, I., Mikhalkin, G., Shustin, E.: Tropical Algebraic Geometry, 2nd edn. Oberwolfach Seminars, vol. 35. Birkhäuser Verlag, Basel (2009)
33.
Karp, R.M.: Reducibility among combinatorial problems. In Miller, R.E., Thatcher, J.W. (eds) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972).CrossRef
34.
Khachiyan, L.: A polynomial algorithm in linear programming. Soviet Math. Doklady 20, 191–194 (1979)MATH
35.
36.
Koiran, P., Portier, N., Rojas, J.M.: Counting Tropically Degenerate Valuations and p-adic Approaches to the Hardness of the Permanent. Submitted for publication, also available as Math ArXiV preprint 1309.0486
37.
Lee, T.-L., Li, T.-Y.: Mixed volume computation in solving polynomial systems. In: Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 97–112. AMS (2011)
38.
Litvinov, G.L., Sergeev, S.N. (eds) Tropical and Idempotent Mathematics, International Workshop TROPICAL-07 (Tropical and Idempotent Mathematics, August 25—30, 2007. Independent University, Contemporary Mathematics, vol. 495. AMS (2009)
39.
Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry, AMS Graduate Studies in Mathematics, vol. 161, AMS (2015, to appear).
40.
Matveev, E.M.: An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II. Izv. Ross. Akad. Nauk Ser. Mat. 64(6), 125–180 (2000); translation in Izv. Math. 64(6), 1217–1269 (2000)
41.
42.
Müller, S., Feliu, E., Regensburger, G., Conradi, C., Shiu, A., Dickenstein, A.: Sign conditions for injectivity of generalized polynomial maps with applications to chemical reaction networks and real algebraic geometry. Math ArXiV preprint 1311.5493
43.
Nesterenko, Y.: Linear Forms in Logarithms of Rational Numbers. Diophantine Approximation (Cetraro, 2000). Lecture Notes in Math., vol. 1819, pp. 53–106. Springer, Berlin (2003)
44.
Newton, I.: Letter to Oldenburg dated 1676 Oct 24, the correspondence of Isaac Newton, II, pp. 126–127. Cambridge University Press, Cambridge (1960)
45.
Ng, CTD., Barketau, M.S., Cheng, T.C.E., Kovalyov, M.Y.: Product Partition and related problems of scheduling and systems reliability: Computational complexity and approximation. Eur. J. Oper. Res. 207, 601–604 (2010)CrossRefMATHMathSciNet
46.
47.
Ning, Y., Avendaño, M.E., Mortari, D.: Sequential design of satellite formations with invariant distances. AIAA J. Spacecraft Rockets 48(6), 1025–1032 (2011)CrossRef
48.
49.
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1995)
50.
Phillipson, K.R., Rojas, J.M.: \(\mathcal{A}\)-discriminants, and their cuttings, for complex exponents (2014, in preparation)
51.
Pin, J.-E.: Tropical semirings. Idempotency (Bristol, 1994), Publ. Newton Inst., 11, pp. 50–69. Cambridge Univ. Press, Cambridge (1998)
52.
Plaisted, D.A.: New NP-hard and NP-complete polynomial and integer divisibility problems. Theor. Comput. Sci. 31(1–2), 125–138 (1984)CrossRefMATHMathSciNet
53.
Schrijver, A.: Theory of Linear and Integer Programming. Wiley (1986)
54.
Shub, M., Smale, S.: The complexity of Bezout’s theorem I: Geometric aspects. J. Am. Math. Soc. 6, 459–501 (1992)MathSciNet
55.
Shub, M., Smale, S.: The Complexity of Bezout’s theorem II: Volumes and Probabilities. In: Eyssette, F., Galligo, A. (eds) Computational Algebraic Geometry, pp. 267–285. Birkhauser (1992)
56.
57.
Shub, M., Smale, S.: The complexity of Bezout’s theorem IV: Probability of success; extensions. SIAM J. Numer. Anal. 33(1), 128–148 (1996)CrossRefMATHMathSciNet
58.
59.
Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Cengage Learning (2012)
60.
61.
Smale, S.: Mathematical Problems for the Next Century. Mathematics: Frontiers and Perspectives, pp. 271–294. Amer. Math. Soc., Providence (2000)
62.
Sommese, A.J., Wampler, C.W.: The Numerical Solution to Systems of Polynomials Arising in Engineering and Science. World Scientific, Singapore (2005)CrossRef
63.
Spielman, D., Teng, S.H.: Smoothed analysis of termination of linear programming algorithms. Math. Program. Ser. B 97 (2003)
64.
Verschelde, J.: Polynomial homotopy continuation with PHCpack. ACM Commun. Comput. Algebra 44(4), 217–220 (2010)MathSciNet
65.
Viro, O.Y.: Dequantization of real algebraic geometry on a logarithmic paper. In: Proceedings of the 3rd European Congress of Mathematicians. Progress in Math, vol. 201, pp. 135–146. Birkhäuser (2001)
66.
Metadaten
Titel
Polynomial-Time Amoeba Neighborhood Membership and Faster Localized Solving
verfasst von
Eleanor Anthony
Sheridan Grant
Peter Gritzmann
J. Maurice Rojas
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Topological and Statistical Methods for Complex Data

Print ISBN: 978-3-662-44899-1

Electronic ISBN: 978-3-662-44900-4

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-44900-4_15

Premium Partner

    Bildnachweise