nach oben

Foundations of Computational Mathematics

Erschienen in:

01.02.2014

Discrete Morse Theoretic Algorithms for Computing Homology of Complexes and Maps

Erschienen in: Foundations of Computational Mathematics | Ausgabe 1/2014

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We provide explicit and efficient reduction algorithms based on discrete Morse theory to simplify homology computation for a very general class of complexes. A set-valued map of top-dimensional cells between such complexes is a natural discrete approximation of an underlying (and possibly unknown) continuous function, especially when the evaluation of that function is subject to measurement errors. We introduce a new Morse theoretic preprocessing framework for deriving chain maps from such set-valued maps, and hence provide an effective scheme for computing the morphism induced on homology by the approximated continuous function.

Vorheriger Artikel Remote Sensing via ℓ 1-Minimization

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

See [5] for a description of a complex in ℝ⁸ with approximately 4.5×10⁶ vertices that arises from the study of natural images.

As indicated earlier, homology is computed via Smith normal form all these preprocessing algorithms can be interpreted algebraically. The difference is that the chain complex is constructed as late as possible and the algebraic operations are often motivated by geometric and combinatorial considerations.

As is shown in [25], there are relationships between these two settings.

M. Allili, T. Kaczynski, An algorithmic approach to the construction of homomorphisms induced by maps in homology, Trans. Am. Math. Soc. 352(5), 2261–2281 (2000). CrossRefMATHMathSciNet

M. Allili, T. Kaczynski, Geometric construction of a coboundary of a cycle, Discrete Comput. Geom. 25(1), 125–140 (2001). CrossRefMATHMathSciNet

Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, P. Pilarczyk, A database schema for the analysis of global dynamics of multiparameter systems, SIAM J. Appl. Dyn. Syst. 8, 757–789 (2009). CrossRefMATHMathSciNet

CAPD::RedHom, http://redhom.ii.uj.edu.pl.

G. Carlsson, Topology and data, Bull., New Ser., Am. Math. Soc. 46(2), 255–308 (2009). CrossRefMATHMathSciNet

M.K. Chari, On discrete Morse functions and combinatorial decompositions, Discrete Math. 217(1–3), 101–113 (2000). Formal power series and algebraic combinatorics (Vienna, 1997). CrossRefMATHMathSciNet

CHomP, http://chomp.rutgers.edu.

C.J.A. Delfinado, H. Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Comput. Aided Geom. Des. 12(7), 771–784 (1995). Grid generation, finite elements, and geometric design. CrossRefMATHMathSciNet

P. Dłotko, R. Ghrist, M. Juda, M. Mrozek, Distributed computation of coverage in sensor networks by homological methods, Appl. Algebra Eng. Commun. Comput. 23, 29–58 (2012). CrossRefMATH

10.

P. Dłotko, T. Kaczynski, M. Mrozek, T. Wanner, Coreduction homology algorithm for regular CW-complexes, Discrete Comput. Geom. 46, 361–388 (2011). CrossRefMATHMathSciNet

11.

J.-G. Dumas, F. Heckenbach, D. Saunders, V. Welker, Computing simplicial homology based on efficient smith normal form algorithms, in Algebra, Geometry, and Software Systems, ed. by M. Joswig, N. Takayama (2003), pp. 177–206. CrossRef

12.

H. Edelsbrunner, J. Harer, Persistent homology—a survey, in Surveys on Discrete and Computational Geometry. Contemp. Math., vol. 453 (Am. Math. Soc., Providence, 2008), pp. 257–282. CrossRef

13.

H. Edelsbrunner, J.L. Harer, Computational Topology (Am. Math. Soc., Providence, 2010). An introduction. MATH

14.

R. Forman, Morse theory for cell complexes, Adv. Math. 134, 90–145 (1998). CrossRefMATHMathSciNet

15.

R. Ghrist, Barcodes: the persistent topology of data, Bull., New Ser., Am. Math. Soc. 45(1), 61–75 (2008). CrossRefMATHMathSciNet

16.

R. Ghrist, Three examples of applied and computational homology, Nieuw Arch. Wiskd. 9(2), 122–125 (2008). MATHMathSciNet

17.

S. Harker, K. Mischaikow, M. Mrozek, V. Nanda, H. Wagner, M. Juda, P. Dłotko, The efficiency of a homology algorithm based on discrete Morse theory and coreductions, in Proceedings of the 3rd International Workshop on Computational Topology in Image Context, vol. 1 (2010), pp. 41–47.

18.

A. Hatcher, Algebraic Topology (Cambridge University Press, Cambridge, 2002). MATH

19.

T. Kaczynski, K. Mischaikow, M. Mrozek, Computing homology, Homol. Homotopy Appl. 5(2), 233–256 (2003). Algebraic topological methods in computer science (Stanford, CA, 2001). CrossRefMATHMathSciNet

20.

T. Kaczynski, K. Mischaikow, M. Mrozek, Computational Homology. Applied Mathematical Sciences, vol. 157 (Springer, Berlin, 2004). MATH

21.

T. Kaczynski, M. Mrozek, M. Ślusarek, Homology computation by reduction of chain complexes, Comput. Math. Appl. 35(4), 59–70 (1998). CrossRefMATHMathSciNet

22.

W.D. Kalies, K. Mischaikow, G. Watson, Cubical approximation and computation of homology, in Conley Index Theory. Banach Center Publ., vol. 47, Warsaw, 1997 (Polish Acad. Sci, Warsaw, 1999), pp. 115–131.

23.

D. Kozlov, Combinatorial Algebraic Topology. Algorithms and Computation in Mathematics, vol. 21 (Springer, Berlin, 2008). CrossRefMATH

24.

S. Lefschetz, Algebraic Topology. American Mathematical Society Colloquium Publications, vol. 27 (Am. Math. Soc., New York, 1942). MATH

25.

K. Mischaikow, M. Mrozek, P. Pilarczyk, Graph approach to the computation of the homology of continuous maps, Found. Comput. Math. 5(2), 199–229 (2005). CrossRefMATHMathSciNet

26.

M. Mrozek, B. Batko, The coreduction homology algorithm, Discrete Comput. Geom. 41, 96–118 (2009). CrossRefMATHMathSciNet

27.

M. Mrozek, P. Pilarczyk, N. Żelazna, Homology algorithm based on acyclic subspace, Comput. Math. Appl. 55, 2395–2412 (2008). CrossRefMATHMathSciNet

28.

M. Mrozek, T. Wanner, Coreduction homology algorithm for inclusions and persistent homology, Comput. Math. Appl. 60(10), 2812–2833 (2010). CrossRefMATHMathSciNet

29.

M. Mrozek, M. Żelawski, A. Gryglewski, S. Han, A. Krajniak, Homological methods for extraction and analysis of linear features in multidimensional images, Pattern Recognit. 45, 285–298 (2012). CrossRef

30.

Perseus, http://www.math.rutgers.edu/~vidit/perseus.html.

31.

B.D. Saunders, Z. Wan, Smith normal form of dense integer matrices, fast algorithms into practice, in Internat. Symp. Symbolic Algebraic Comput. (2004), pp. 274–281.

32.

E.H. Spanier, Algebraic Topology (McGraw-Hill, New York, 1966). MATH

33.

A.W. Tucker, Cell spaces, Ann. of Math. (2) 37(1), 92–100 (1936). CrossRefMathSciNet

Titel: Discrete Morse Theoretic Algorithms for Computing Homology of Complexes and Maps
Publikationsdatum: 01.02.2014
Erschienen in: Foundations of Computational Mathematics / Ausgabe 1/2014
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-013-9145-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2014

Smale’s Fundamental Theorem of Algebra Reconsidered

Target Identification Using Dictionary Matching of Generalized Polarization Tensors

Restricted Normal Cones and Sparsity Optimization with Affine Constraints

The Magnus Expansion, Trees and Knuth’s Rotation Correspondence

Remote Sensing via ℓ 1-Minimization