Office Hour: Monday 3:30 - 4:30pm
: yusu at
Topology aims at studying intrinsic structures of a given object or space. It is a powerful tool for identifying, describing, and characterizing essential features of functions and spaces. Indeed, in recent years topological methods have been availed as new promising tools for analyzing complex and diverse data. Fundamental progress has been made in both the theoretical and algorithmic development in computational topology. The resulting methods have been successfully applied in a broad range of fields, including in machine learning, graphics and visualization, computational neuron science, material science and computational biology.
This course aims to provide an introduction to basic concepts and topological structures behind these recent developments in computational topology, as well as algorithms to compute them. Some topics are: basics in topology, popular choices of simplicial complexes, persistent homology, contour trees and Reeb's graph, discrete Morse complex, topology inference, the Mappper methodology (for summarizing multivariate fields), and structure behind hierarchical clustering. The course will particularly focus on providing a computational view of these topics. Examples of applications to topological data analysis will be given throughout the course, accompanying various topics.
A tentative list of topics is here in [pdf].
There is no book that is exactly suitable for this class. I will provide detailed lecture notes for most classes.
You can check out the course material by Tamal Dey here for reference.
Computational Topology: An Introduction, by H. Edelsbrunner and J. Harer, AMS Press, 2009.
Some Online course notes by Herbert Edelsbrunner on computational topology is available here.
Algebraic Topology, by A. Hatcher, Cambridge University Press, 2002.
Online version is available here at the author's webpage.
An Introduction to Morse Theory, by Y. Matsumoto, Amer. Math. Soc., Providence, Rhode Island, 2002.
Elements of Algebraic Topology, by J. R. Munkres, Perseus, Cambridge, Massachusetts, 1984.
- Grading policy :
- There is a final survey or project (including a short presentation and a report).
The final grades are based on:
Survey / project: 90%, Class participation: 10%
Proposal Due: Oct. 15th
Final presentation: Dec 11th, 12pm--2pm, DL480.
Final report Due: Dec 11th
The presentation is 10 minutes (you should prepare for 8 minutes, including 2 minutes for questions). The final report should be at least 4 pages for projects, and at least 8 pages for surveys. The report should clearly describe the motivation of your project, what you have done, and your findings (this could be just some observations from your exploration).
You can form a team of at most 2 people for a project -- in which case, the final report for project needs to be 6 pages, and the contribution from each individual team member has to be detailed.
- Lecture Topics:
- A tentative list of topics is here in [pdf].
Topic 0: Introduction to computational topology. (slides [ppt], [pdf])
Topic 1: Basics (lecture notes [pdf]) (slides used in class [pptx])
- Topic 2: Simplicial complexes (lecture notes [pdf])(slides used in class [pptx])
- Topic 3: Simplicial homology and computation (lecture notes [pdf])(slides used in class [pptx])
- Topic 4: Persistent homology and computation (lecture notes [pdf])(slides used in class [pptx])
- Topic 5: Function-induced persistence (lecture notes [pdf]), (slides used in class [pptx])
- Topic 6: More about persistence and applications (slides used in class [pptx])
- Topic 7: Reeb graphs, contour trees, and Mapper (slides used in class [Part I (pptx)], [Part II (pdf)]).
- Topic 8: A brief introduction to discrete Morse theory and graph reconstruction (slides used in class [pptx])
- Software / Tools resources:
- Computing Persistent homology:
- The Ripser library is available here . It contains a memory+time efficient algorithm for computing persistent homology for Rips filtration.
- The Gudhi library is available here . This includes currently the most efficient algorithm for computing persistent homology for arbitrary simplicial complex. The references for the algorithm is available on the Gudhi webpage.
- The PHAT library is available here .
This algorithm is also efficient, and the algorithm is closer to the Gaussian elimination we described in class, thus potentially easier to play with if you need to modify the code.
The references for the code is available on the website.
There is also a parallel version DIPHA for effecient computation of PH on distributed systems, which is available here.
- The Dionysus library is one of the most comprehensive packages, which contains many persistence related computation, including levelset zigzag persistence. It is available here. It is written in C++ and reasonably efficient.
- The JavaPles library is a Matlab and Java-based system. It is available here . It can automatically compute Vietoris-Rips, witness and lazy-witness complexes from input finite metric spaces (e.g point clouds data in a feature space) to further build persistent homology. The webpage also contains tutorial etc.
- The SimPers package is specifically for persistence of a filtration connected by simplicial maps. It is available here .
- The Sophia package is also specifically for persistence of a filtration connected by simplicial maps. Its practical performance can be better than SimPers. It is available here .
- Computing Bottleneck / Wasserstein distance between persistence diagrams:
- The Hera package is available here. It
computes the bottleneck or Wasserstein distances between two persistence diagrams efficiently.
- Compute persistence for simplicial maps:
- Sparsification / approximation:
- The SimBa package is available here . It produces approximate persistence diagrams for Rips filtration of a set of points in the Euclidean space or in general metric space. It is originally developed by Dayu Shi, working with Dr. Tamal Dey and myself, and currently maintained by Sayan Mandal.
- The Sophia package is available here. It produces approximate persistence diagrams for Rips filtration of a set of points in the Euclidean space.
- Graphs, Reeb graph / contour tree related:
- The code to compute persistence diagrams for a function defined on a graph can be downloaded here.
The code to compute the persistence-distortion distance for comparing two metric graphs can be downloaded here. Both are developed by Dayu Shi, working with Dr. Tamal Dey and myself.
- The Denali software package for visualizing terrain metaphor is available here. The package includes code to compute contour trees for a scalar field.
- The randomized algorithmm for computing Reeb graph for arbitrary simplicial complex can be downloaded here.
- Discrete Morse complex:
- The graph reconstruction based on discrete Morse complex is available here. It takes arbitrary simplicial complex + a vertex-wise function, or a 2D / 3D cubic grid with vertex-wise function, as input. Examples for road network reconstructions are included.
- The DisPerse package is available here . The software only takes 2D or 3D volumetric data, or Delaunay triangulations.
- Some of the past students final presentation slides from previous years can be found here (not a complete list).
- Suggested Readings / Related Resources:
- The final presentation for your project / survey will happen on Dec 11, 12pm--2pm in DL480.
The final report of your project/survey is due on the same day.
- A one-page project/survey proposal is due on Oct. 15th, to describe briefly your course project / survey (what it is about, and motivation etc). Please send the proposal to me via email.