Top

Foundations of Computational Mathematics

Published in:

01-08-2016

Discrete Morse Theory for Computing Cellular Sheaf Cohomology

Authors: Justin Curry, Robert Ghrist, Vidit Nanda

Published in: Foundations of Computational Mathematics | Issue 4/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Sheaves and sheaf cohomology are powerful tools in computational topology, greatly generalizing persistent homology. We develop an algorithm for simplifying the computation of cellular sheaf cohomology via (discrete) Morse theoretic techniques. As a consequence, we derive efficient techniques for distributed computation of (ordinary) cohomology of a cell complex.

previous article Tensor-Sparsity of Solutions to High-Dimensional Elliptic Partial Differential Equations

next article Integrators on Homogeneous Spaces: Isotropy Choice and Connections

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

That is, the complexity of composing two \(d \times d\) matrices with \(\mathbf{R}\)-entries is \(\text {O}(d^\omega )\).

When striving for greater generality, one replaces this requirement by the following local finiteness hypothesis on the covering relation: each \(x \in X\) can have only finitely many y so that \(y \prec x\) or \(x \prec y\).

In principle, any method for constructing acyclic partial matchings on graded posets will suffice, provided that it ensures sheaf compatibility by only matching cell pairs whose restriction maps are invertible.

R. Adler, The Geometry of Random Fields, (Wiley, 1981 and reprinted by SIAM, 2010).

R. Adler and J.E. Taylor, Random Fields and Geometry (Springer, 2009).

P. Alexandroff. Über den allgemeinen Dimensionsbegriff und seine Beziehungen zur elementaren geometrischen Anschauung. Math. Ann., 98, 617–635 (1928).MathSciNetCrossRefMATH

Z. Arai, W. Kalies, H. Kokubu, K. Mischaikow, H. Oka, and Pl. Pilarczyk, A Database Schema for the Analysis of Global Dynamics of Multiparameter Systems, SIAM J. Appl. Dyn. Syst., 8(3), 757–789 (2009).MathSciNetCrossRefMATH

Y. Baryshnikov and R. Ghrist, Target enumeration via Euler characteristic integrals, SIAM J. Appl. Math., 70(3), 825–844 (2009).MathSciNetCrossRefMATH

Y. Baryshnikov and R. Ghrist, Euler integration over definable functions, Proc. Natl. Acad. Sci. USA 107(21), 9525–9530 (2010).MathSciNetCrossRefMATH

S. Basu, A complexity theory of constructible functions and sheaves, Found. Comput. Math., 15(1), 199–279 (2015).MathSciNetCrossRefMATH

E. Batzies and V. Welker. Discrete Morse theory for cellular resolutions. J. Reine Angew. Math., 543:147–168 (2002).MathSciNetMATH

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, Bull. Amer. Math. Soc. (N.S.) 21(1), 1–46 (1989).MathSciNetCrossRefMATH

10.

K. Borsuk. On the imbedding of systems of compacta in simplicial complexes. Fund. Math. 35, 217–234 (1948).MathSciNetMATH

11.

G. E. Bredon. Sheaf Theory, (Springer, 1997)

12.

D. Burghelea and T. K. Dey. Topological persistence for circle-valued maps. Discrete and Computational Geometry, 50(1):1–30 (2011).MathSciNetMATH

13.

G. Carlsson. Topology and data. Bull. Amer. Math. Soc. (N.S.), 46(2), 255–308 (2009).MathSciNetCrossRefMATH

14.

G. Carlsson, V. de Silva, and D. Morozov. Zigzag persistent homology and real-valued functions. Proc. Ann. Sympos. Comp. Geom., 247–256 (2009).

15.

M. K. Chari. On discrete Morse functions and combinatorial decompositions. Discrete Math., 217(1–3) 101–113 (2000).MathSciNetCrossRefMATH

16.

J. Curry. Sheaves, cosheaves and applications. arXiv:1303.3255[math.AT](2013).

17.

J. Curry, R. Ghrist, and M. Robinson. Euler calculus and its applications to signals and sensing. Proc. Sympos. Appl. Math. 70, 75–145 (2012).MathSciNetCrossRefMATH

18.

V. de Silva and R. Ghrist. Coordinate-free coverage in sensor networks with controlled boundaries via homology, Intl. J. Robotics Research 25, 1205–1222 (2006).CrossRefMATH

19.

V. de Silva and R. Ghrist. Coverage in sensor networks via persistent homology, Algebr. Geom. Topol., 7, 339–358 (2007).MathSciNetCrossRefMATH

20.

V. de Silva, D. Morozov, and M. Vejdemo-Johansson. Persistent Cohomology and Circular Coordinates. Discrete Comput. Geom., 45(4), 737–759 (2011).MathSciNetCrossRefMATH

21.

V. de Silva, E. Munch, and A. Patel. Categorified Reeb graphs. arXiv:1501.04147[cs.CG], (2015).

22.

H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom., 28(4):511–533 (2002).MathSciNetCrossRefMATH

23.

H. Edelsbrunner, J. Harer, Computational Topology. An Introduction, (American Mathematical Society, 2010).

24.

M. Farber. Topological Complexity of Motion Planning. Discrete Comput. Geom. 29, 211–221 (2003).MathSciNetCrossRefMATH

25.

M. Farber. Collision free motion planning on graphs. In Algorithmic Foundations of Robotics IV, (M. Erdmann, D. Hsu, M. Overmars, A. F. van der Stappen eds.), Springer, 2005, pp. 123–138.

26.

R. Forman. Morse theory for cell complexes. Advances in Mathematics, 134(1), 90–145 (1998).MathSciNetCrossRefMATH

27.

R. Ghrist, Configuration spaces, braids, and robotics. Lecture Note Series, Inst. Math. Sci., NUS, vol. 19, World Scientific, 263–304 (2010).

28.

R. Ghrist, Elementary Applied Topology, (Createspace, 2014).

29.

R. Ghrist and Y. Hiraoka. Sheaves for network coding. In Proc. NOLTA: Nonlinear Theory and Applications, 266–269, (2011).

30.

R. Ghrist and S. Krishnan. A topological max-flow-min-cut theorem. In Proc. Global Sig. Inf. Proc., 815–818 (2013).

31.

J. A. Goguen. Sheaf semantics for concurrent interacting objects. Mathematical Structures in Computer Science, 2(2) 159–191, (1992).MathSciNetCrossRefMATH

32.

S. Harker, K. Mischaikow, M. Mrozek, and V. Nanda. Discrete Morse theoretic algorithms for computing homology of complexes and maps. Found. Comput.l Math. 14(1), 151–184 (2014).MathSciNetCrossRefMATH

33.

G. Haynes, F. Cohen, and D. Koditschek. Gait Transitions for Quasi-Static Hexapedal Locomotion on Level Ground. in International Symposium of Robotics Research, Springer, 2011, pp 105–121.

34.

T. Kaczynski, K. Mischaikow, and M. Mrozek. Computational Homology (Springer-Verlag, 2004).

35.

D. Kozlov. Discrete Morse theory for free chain complexes. C. R. Math., 340(12), 867–872 (2005).MathSciNetCrossRefMATH

36.

S. Krishnan. Flow-cut duality for sheaves on graphs. arXiv:1409.6712[math.AT], (2014).

37.

J. Leray. Sur la forme des espaces topologiques et sur les points fixes des représentations. J. Math. Pures Appl., 24(9), 95–167 (1945).MathSciNetMATH

38.

R. H. Lewis and A. Zomorodian. Multicore homology. arXiv:1407.2275 [cs.CG], (2014).

39.

R. MacPherson and A. Patel. Private communication, 2013.

40.

J. McCleary. A User’s Guide to Spectral Sequences, (Cambridge University Press, 2001).

41.

K. Mischaikow and M. Mrozek, Conley Index Theory. In Handbook of Dynamical Systems II: Towards Applications, (B. Fiedler, ed.) North-Holland, 2002, pp 393–460.

42.

K. Mischaikow and V. Nanda. Morse theory for filtrations and efficient computation of persistent homology. Discrete Comput. Geom., 50(2), 330–353 (2013).MathSciNetCrossRefMATH

43.

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

44.

J. Munkres. Elements of Algebraic Topology. (Benjamin/Cummings, 1984).

45.

S. Ramanan. Global Calculus. (American Mathematical Society, 2005).

46.

M. Robinson. The Nyquist theorem for cellular sheaves. Proc. Sampling Theory and Applications, 2013, pp 293–296.

47.

P. Schapira. Operations on constructible functions. J. Pure Appl. Algebra, 72(1), 83–93 (1991).MathSciNetCrossRefMATH

48.

P. Schapira. Tomography of constructible functions. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer, 1995, pp. 427–435.

49.

G. Segal. Classifying spaces and spectral sequences. Inst. Hautes Études Sci. Publ. Math., 34, 105–112, (1968).MathSciNetCrossRefMATH

50.

A. Shepard. A Cellular Description of the Derived Category of a Stratified Space. Brown University PhD Thesis, 1985.

51.

E. Sköldberg. Morse theory from an algebraic viewpoint. Trans. Amer. Math. Soc., 358(1), 115–129 (2006).MathSciNetCrossRefMATH

52.

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

53.

M. Vybornov. Sheaves on triangulated spaces and Koszul duality. arXiv:math/9910150[math.AT], 2000.

54.

C. A. Weibel. An Introduction to Homological Algebra, (Cambridge University Press, 1995).

55.

J. H. C. Whitehead. Combinatorial homotopy I. Trans. Amer. Math. Soc., 55(5), 453–496 (1949).MathSciNetMATH

56.

A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete Comput. Geom., 33(2), 249–274 (2005).MathSciNetCrossRefMATH

57.

A. Zomorodian and G. Carlsson. Localized homology. Comput. Geom., 41(3), 126–148, (2008).MathSciNetCrossRefMATH

Title: Discrete Morse Theory for Computing Cellular Sheaf Cohomology
Authors: Justin Curry
Robert Ghrist
Vidit Nanda
Publication date: 01-08-2016
Publisher: Springer US
Published in: Foundations of Computational Mathematics / Issue 4/2016
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-015-9266-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2016

Tensor-Sparsity of Solutions to High-Dimensional Elliptic Partial Differential Equations

A Primal-Dual Formulation for Certifiable Computations in Schubert Calculus

Integrators on Homogeneous Spaces: Isotropy Choice and Connections

On Tensor Completion via Nuclear Norm Minimization

Sharp MSE Bounds for Proximal Denoising

Premium Partner