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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards MyNewsletter Firmensuche
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
Sustainability in Automotive

Gesamtlebenszyklus wird immer wichtiger

In der Digitalkonferenz am 5. Dezember 2024 geht es um die wachsende Bedeutung der Kreislaufwirtschaft in der Automobilindustrie und wie nachhaltige Werkstoffe sowie wiederverwendbare Komponenten dazu beitragen können.
Erweiterte Suche
Anmelden
nach oben
Foundations of Computational Mathematics
Erschienen in:

04.08.2017

Computing the Homology of Real Projective Sets

verfasst von: Felipe Cucker, Teresa Krick, Michael Shub

Erschienen in: Foundations of Computational Mathematics | Ausgabe 4/2018

Einloggen

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

search-config
loading …

Abstract

We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of real projective varieties. Here numerical means that the algorithm is numerically stable (in a sense to be made precise). Its cost depends on the condition of the input as well as on its size and is singly exponential in the number of variables (the dimension of the ambient space) and polynomial in the condition and the degrees of the defining polynomials. In addition, we show that outside of an exceptional set of measure exponentially small in the size of the data, the algorithm takes exponential time.
Vorheriger Artikel Shape-Aware Matching of Implicit Surfaces Based on Thin Shell Energies
Nächster Artikel Optimal Rates for Regularization of Statistical Inverse Learning Problems

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
Literatur
1.
E.L. Allgower and K. Georg. Numerical Continuation Methods. Springer-Verlag, 1990.
2.
D. Amelunxen and M. Lotz. Average-case complexity without the black swans. To appear at J. Compl. Available at arXiv:​1512.​09290, 2016.
3.
S. Basu. Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time. Found. Comput. Math., 8(1):45–80, 2008.MathSciNetCrossRefMATH
4.
S. Basu, R. Pollack, and M.-F. Roy. Computing the first Betti number of a semi-algebraic set. Found. Comput. Math., 8(1):97–136, 2008.MathSciNetCrossRefMATH
5.
A. Björner. Topological methods. In R. Graham, M. Grotschel, and L. Lovasz, editors, Handbook of Combinatorics, pages 1819–1872. North-Holland, Amsterdam, 1995.
6.
L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.
7.
L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc., 21:1–46, 1989.MathSciNetCrossRefMATH
8.
P. Bürgisser and F. Cucker. Counting complexity classes for numeric computations II: Algebraic and semialgebraic sets. J. Compl., 22:147–191, 2006.MathSciNetCrossRefMATH
9.
P. Bürgisser and F. Cucker. Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math., 9:135–170, 2009.MathSciNetCrossRefMATH
10.
P. Bürgisser and F. Cucker. Condition, volume 349 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 2013.MATH
11.
D. Cheung and F. Cucker. Solving linear programs with finite precision: II. Algorithms. J. Compl., 22:305–335, 2006.MathSciNetMATH
12.
G.E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic deccomposition, volume 33 of Lect. Notes in Comp. Sci., pages 134–183. Springer-Verlag, 1975.
13.
14.
F. Cucker, H. Diao, and Y. Wei. Smoothed analysis of some condition numbers. Numer. Lin. Alg. Appl., 13:71–84, 2006.MathSciNetCrossRefMATH
15.
F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. I: Complexity and accuracy. J. Compl., 24:582–605, 2008.MathSciNetCrossRefMATH
16.
F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis. J. Fixed Point Theory Appl., 6:285–294, 2009.MathSciNetCrossRefMATH
17.
F. Cucker, T. Krick, G. Malajovich, and M. Wschebor. A numerical algorithm for zero counting. III: Randomization and condition. Adv. Applied Math., 48:215–248, 2012.MathSciNetCrossRefMATH
18.
F. Cucker and J. Peña. A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine. SIAM J. Optim., 12:522–554, 2002.MathSciNetCrossRefMATH
19.
F. Cucker and S. Smale. Complexity estimates depending on condition and round-off error. Journal of the ACM, 46:113–184, 1999.MathSciNetCrossRefMATH
20.
Carlos D’Andrea, Teresa Krick, and Martín Sombra. Heights of varieties in multiprojective spaces and arithmetic Nullstellensätze. Ann. Sci. Éc. Norm. Supér. (4), 46(4):549–627 (2013), 2013.
21.
22.
H. Edelsbrunner and J.L. Harer. Computational topology. American Mathematical Society, Providence, RI, 2010. An introduction.
23.
E. Kostlan. Complexity theory of numerical linear algebra. J. of Computational and Applied Mathematics, 22:219–230, 1988.MathSciNetCrossRefMATH
24.
M. Lotz. On the volume of tubular neighborhoods of real algebraic varieties. Proc. Amer. Math. Soc., 143(5):1875–1889, 2015.MathSciNetCrossRefMATH
25.
P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39:419–441, 2008.MathSciNetCrossRefMATH
26.
V. Noferini and A. Townsend. Numerical instability of resultant methods for multidimensional rootfinding. To appear at SIAM J. Num. Analysis. Available at arXiv:​1507.​00272.
27.
J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I. Journal of Symbolic Computation, 13:255–299, 1992.MathSciNetCrossRefMATH
28.
29.
J. Renegar. Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim., 5:506–524, 1995.MathSciNetCrossRefMATH
30.
J. Renegar. Linear programming, complexity theory and elementary functional analysis. Math. Program., 70:279–351, 1995.MathSciNetMATH
31.
P. Scheiblechner. On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety. J. Complexity, 23(3):359–379, 2007.MathSciNetCrossRefMATH
32.
P. Scheiblechner. Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties. Found. Comput. Math., 12(5):541–571, 2012.MathSciNetCrossRefMATH
33.
M. Shub and S. Smale. Complexity of Bézout’s Theorem I: geometric aspects. Journal of the Amer. Math. Soc., 6:459–501, 1993.MathSciNetMATH
34.
M. Shub and S. Smale. Complexity of Bézout’s Theorem II: volumes and probabilities. In F. Eyssette and A. Galligo, editors, Computational Algebraic Geometry, volume 109 of Progress in Mathematics, pages 267–285. Birkhäuser, 1993.
35.
M. Shub and S. Smale. Complexity of Bézout’s Theorem III: condition number and packing. Journal of Complexity, 9:4–14, 1993.MathSciNetCrossRefMATH
36.
M. Shub and S. Smale. Complexity of Bézout’s Theorem V: polynomial time. Theoret. Comp. Sci., 133:141–164, 1994.CrossRefMATH
37.
M. Shub and S. Smale. Complexity of Bézout’s Theorem IV: probability of success; extensions. SIAM J. of Numer. Anal., 33:128–148, 1996.CrossRefMATH
38.
S. Smale. Newton’s method estimates from data at one point. In R. Ewing, K. Gross, and C. Martin, editors, The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics. Springer-Verlag, 1986.
39.
A. Storjohann. Nearly optimal algorithms for computing Smith normal forms of integer matrices. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’96), pages 267–274. ACM Press, 1996.
40.
H.R. Wüthrich. Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper. In E. Specker and V. Strassen, editors, Komplexität von Entscheidungsproblemen, volume 43 of Lect. Notes in Comp. Sci., pages 138–162. Springer-Verlag, 1976.
Metadaten
Titel
Computing the Homology of Real Projective Sets
verfasst von
Felipe Cucker
Teresa Krick
Michael Shub
Publikationsdatum
04.08.2017
Verlag
Springer US
Erschienen in
Foundations of Computational Mathematics / Ausgabe 4/2018
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-017-9358-8

Weitere Artikel der Ausgabe 4/2018

Numerical Computation of Galois Groups

An Explicit Isometric Reduction of the Unit Sphere into an Arbitrarily Small Ball

A Lagrangian Scheme à la Brenier for the Incompressible Euler Equations

Distortion Varieties

Optimal Rates for Regularization of Statistical Inverse Learning Problems

Shape-Aware Matching of Implicit Surfaces Based on Thin Shell Energies

  • Open Access

Premium Partner

    Bildnachweise