Discrete Morse Theory

​

​

​

​

​

​

​

Julien Tierny

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

​

​

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

​

​

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

​

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

• Topological abstractions

​

​

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

• Topological abstractions
• Critical points

​

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

• Topological abstractions
• Critical points

​

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

• Topological abstractions
• Critical points
• Persistence diagrams
• Persistence curve

​

​

​

Persistence simplification

​

​

• Simplify the data
• Retain only persistent features

​

• Algorithms
• Edelsbrunner et al. 2006, Attali et al. 2009, Tierny and Pascucci 2012, Bauer et al. 2012, Lukasczyk et al. 2020

​

​

​

Limitations of Persistence Diagrams

​

• Input PL scalar data
• ​

​

​

​

• Topological abstractions
• Critical points
• Persistence diagrams
• Persistence curve

​

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

• Topological abstractions
• Critical points
• Persistence diagrams
• Persistence curves
• Reeb graphs

​

​

Piecewise linear setting

​

• Input PL scalar data
• ​

​

​

​

• Topological abstractions
• Critical points
• Persistence diagrams
• Persistence curves
• Reeb graphs

​

​

Reeb graph segmentation

Reeb graph segmentation

TopoAngler [Bock et al., IEEE VIS 2017]

Mapper

Mapper

Mapper

Mapper

Mapper

• Singh et al. 2007

​

​

​

​

​

Limitations of Reeb graphs

​

• Input PL scalar data
• ​

​

​

​

​

​

Limitations of Reeb graphs

Limitations of Reeb graphs

Limitations of Reeb graphs

Limitations of Reeb graphs

Morse complex

• Motivation
• Complete yet concise topological representation
• Descending manifold
• Given a critical point p, points of integral lines terminating in p

​

​

​

Morse complex

• Motivation
• Complete yet concise topological representation
• Descending manifold
• Given a critical point p, points of integral lines terminating in p
• Morse complex
• All descending manifolds

​

​

​

Morse complex

• Motivation
• Complete yet concise topological representation
• Descending manifold
• Given a critical point p, points of integral lines terminating in p
• Morse complex
• All descending manifolds

​

​

​

Morse complex

• Motivation
• Complete yet concise topological representation
• Descending manifold
• Given a critical point p, points of integral lines terminating in p
• Morse complex
• All descending manifolds

​

​

​

Morse-Smale complex

• Intersection
• Morse complex of f
• Morse complex of -f

​

​

​

​

​

Morse-Smale complex

• Intersection
• Morse complex of f
• Morse complex of -f

​

​

​

​

​

​

​

Morse-Smale complex

• Intersection
• Morse complex of f
• Morse complex of -f
• Persistence simpliciation
• Hierarchical complexes

​

​

​

​

​

​

Applications

Live demo

Applications

Applications

Applications

Applications

Applications

Applications

Valid if

​

​

​

• Ascending and descending manifolds
• Transversal intersection

Valid if

​

​

​

• Ascending and descending manifolds
• Transversal intersection

Valid if

​

​

​

• Ascending and descending manifolds
• Transversal intersection

Valid if

​

​

​

• Ascending and descending manifolds
• Transversal intersection

Properties

• Generic CW complex
• 1D cells: index d to d+1

​

​

​

Properties

• Generic CW complex
• 1D cells: index d to d+1

​

• 2-manifolds
• 2D cells: quadrangles
• Simple saddles: valence 4
• Extrema: arbitrary valence

​

Properties

• Generic CW complex
• 1D cells: index d to d+1

​

• 2-manifolds
• 2D cells: quadrangles
• Simple saddles: valence 4
• Extrema: arbitrary valence

​

• 3-manifolds
• 3D cells: arbitrary number of faces
• Polygonal faces: quadrangles

Algorithms

• PL setting
• 2-manifolds
• Edelsbrunner et al. 2000
• Bremer et al. 2003

​

​

​

​

​

​

Algorithms

• PL setting
• 2-manifolds
• Edelsbrunner et al. 2000
• Bremer et al. 2003

​

• 3-manifolds
• Edelsbrunner et al. 2003
• Gyulassy et al. 2007

​

​

​

​

Algorithms

• PL setting
• 2-manifolds
• Edelsbrunner et al. 2000
• Bremer et al. 2003

​

• 3-manifolds
• Edelsbrunner et al. 2003
• Gyulassy et al. 2007

​

• Challenges
• Saddle unfolding
• Transversal intersection
• No known robust implementation

​

​

Algorithms

• PL setting
• 2-manifolds
• Edelsbrunner et al. 2000
• Bremer et al. 2003

​

• 3-manifolds
• Edelsbrunner et al. 2003
• Gyulassy et al. 2007

​

• Challenges
• Saddle unfolding
• Transversal intersection
• No known robust implementation
• Until Discrete Morse Theory

​

Discrete Morse Theory

• Robin Forman
• “A user’s guide to DMT” 2002

​

• Discrete Morse Function
• Maps each simplex to

​

​

Discrete Morse Theory

• Robin Forman
• “A user’s guide to DMT” 2002

​

• Discrete Morse Function
• Maps each simplex to
• Such that
• ​
• ​

​

​

​

Discrete Morse Theory

• Robin Forman
• “A user’s guide to DMT” 2002

​

• Discrete Morse Function
• Maps each simplex to
• Such that
• ​
• ​

​

• Critical simplices
• ​
• ​

​

Discrete Gradient Field

• Discrete vector
• Pair

​

​

​

​

​

Discrete Gradient Field

• Discrete vector
• Pair

​

• Discrete vector field
• Collection V of pairs
• Each simplex in at most 1 pair

​

​

​

Discrete Gradient Field

• Discrete vector
• Pair

​

• Discrete vector field
• Collection V of pairs
• Each simplex in at most 1 pair

​

• Discrete integral line (v-path)
• Sequence of vectors
• ​

​

​

​

Discrete Gradient Field

• Discrete vector
• Pair

​

• Discrete vector field
• Collection V of pairs
• Each simplex in at most 1 pair

​

• Discrete integral line (v-path)
• Sequence of vectors
• ​

​

​

​

Discrete Gradient Field

• Discrete vector
• Pair

​

• Discrete vector field
• Collection V of pairs
• Each simplex in at most 1 pair

​

• Discrete integral line (v-path)
• Sequence of vectors
• ​

​

​

• Discrete gradient field
• All v-paths are loop free

TODO: backward vpaths (dual)

• TODO
• TODO

​

​

​

​

​

​

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012

​

​

​

​

​

​

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012
• For each dimension i

​

​

​

​

​

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012
• For each dimension i
• For each simplex

​

​

​

​

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012
• For each dimension i
• For each simplex
• Co-facets maximized by

​

​

​

​

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012
• For each dimension i
• For each simplex
• Co-facets maximized by

• Select the minimum co-facet

​

​

​

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012
• For each dimension i
• For each simplex
• Co-facets maximized by

• Select the minimum co-facet

​

• Trivially parallelizable

​

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012
• For each dimension i
• For each simplex
• Co-facets maximized by

• Select the minimum co-facet

​

• Trivially parallelizable

​

• Comparing simplices
• Filtration order (e.g. lexicographic filtration)

​

​

From a filtration to a discrete gradient field

• Steepest descent assignment
• Shrivashankar et al. 2012
• For each dimension i
• For each simplex
• Co-facets maximized by

• Select the minimum co-facet

​

• Trivially parallelizable

​

• Comparing simplices
• Filtration order (e.g. lexicographic filtration)
• Discrete vectors: “apparent” persistent pairs (Ripser, DMS, etc.)

​

Discrete gradient field and persistence

• Critical simplices -> simplices involved in non-trivial pairs
• Play filtration of running example and track persistence pairs

​

​

​

​

​

​

​

Properties

• Unpaired simplices
• Dead-ends for v-paths

​

​

​

​

​

​

​

Properties

• Unpaired simplices
• Dead-ends for v-paths
• Notion of critical simplex

​

​

​

​

​

​

Properties

• Unpaired simplices
• Dead-ends for v-paths
• Notion of critical simplex
• Dimension: index \0/

​

​

​

​

​

Properties

• Unpaired simplices
• Dead-ends for v-paths
• Notion of critical simplex
• Dimension: index \0/
• Manifold domain
• No degenerate critical point! \0/

​

​

​

​

Properties

• Unpaired simplices
• Dead-ends for v-paths
• Notion of critical simplex
• Dimension: index \0/
• Manifold domain
• No degenerate critical point! \0/

​

• Transversal intersection
• Dimensionality of V-paths
• Depends on critical index
• 2D: ascending and descending manifolds on different dimensions

​

​

Properties

• Unpaired simplices
• Dead-ends for v-paths
• Notion of critical simplex
• Dimension: index \0/
• Manifold domain
• No degenerate critical point! \0/

​

• Transversal intersection
• Dimensionality of V-paths
• Depends on critical index
• 2D: ascending and descending manifolds on different dimensions
• Descending manifolds: primal complex
• Ascending manifolds: dual complex

​

Discrete Morse-Smale complex

• Algorithm
• Collect the ascending and descending manifolds*

​

​

​

​

​

​

Discrete Morse-Smale complex

• Algorithm
• Collect the ascending and descending manifolds of each critical cell

​

​

​

​

​

​

Discrete Morse-Smale complex

• Algorithm
• Collect the ascending and descending manifolds of each critical cell

​

• 1-dimensional separatrices
• Descending manifolds of 1-saddles (primal)
• Ascending manifolds of (d-1)-saddles (dual)

​

​

​

​

Discrete Morse-Smale complex

• Algorithm
• Collect the ascending and descending manifolds of each critical cell

​

• 1-dimensional separatrices
• Descending manifolds of 1-saddles (primal)
• Ascending manifolds of (d-1)-saddles (dual)

​

• 2-dimensional separatrices
• Descending manifolds of (d-1)-saddles (primal)
• Ascending manifolds of 1-saddles (dual)

​

​

Discrete Morse-Smale complex

• Algorithm
• Collect the ascending and descending manifolds of each critical cell

​

• 1-dimensional separatrices
• Descending manifolds of 1-saddles (primal)
• Ascending manifolds of (d-1)-saddles (dual)

​

• 2-dimensional separatrices
• Descending manifolds of (d-1)-saddles (primal)
• Ascending manifolds of 1-saddles (dual)

​

• Saddle connectors (3D)
• V-path connecting a 1-saddle to a 2-saddle (intersection)

​

PL matching property

Simplification

• Pre-simplification
• Scalar field simplification

​

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Simplification

• Pre-simplification
• Scalar field simplification

​

• Post-simplification
• Simplifying pairs of critical simplices
• Existence of a unique v-path
• Gradient reversal (domino flip)
• MS-complex update

​

Applications

• Filament extraction
• Molecular interactions
• Paths in porous media
• Cosmic web
• Salient curves in point clouds
• etc.

​

Applications

• Filament extraction
• Molecular interactions
• Paths in porous media
• Cosmic web
• Salient curves in point clouds
• etc.

​

Applications

• Filament extraction
• Molecular interactions
• Paths in porous media
• Cosmic web
• Salient curves in point clouds
• etc.

​

Applications

• Filament extraction
• Molecular interactions
• Paths in porous media
• Cosmic web
• Salient curves in point clouds
• etc.

​

Applications

• Filament extraction
• Molecular interactions
• Paths in porous media
• Cosmic web
• Salient curves in point clouds
• etc.

​

• Cellular segmentation
• Persistent Homology computation
• Manifold reconstruction
• Persistence driven clustering

​

​

​

​

• Video tutorials
• https://topology-tool-kit.github.io/tutorials.html

​

​

​

​

​

​

​

​

​

• Documentation
• https://topology-tool-kit.github.io/documentation.html

​

Take-home message

​

• Morse-Smale complex
• Filament structures
• Cell-like segmentation
• Data clustering
• TDA acceleration
• Complete & concise topological representation

​

• Discrete Morse Theory
• Simple and elegant
• Enables robustness in algorithms
• Compliance with the PL setting
• Challenging boundary handling :(

​

​

​

​

• Video tutorials
• https://topology-tool-kit.github.io/tutorials.html

​

​

​

​

​

​

​

​

​

• Documentation
• https://topology-tool-kit.github.io/documentation.html

​

Overall conclusion

• Topological Data Analysis
• Feature extraction
• Structural information
• Visualization & analysis
• Invariance to affine transformations
• Conciseness & stability
• Small data signatures
• Code is available (TTK, Gudhi)

​

• Perspectives
• Statistical analysis
• Space of topological signatures
• https://erc-tori.github.io/

Saddle unfolding

Persistence diagrams

Reeb graphs

Morse-Smale complexes