Office Hour: Monday 4:00 - 5:00pm
: 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, 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 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: March 21st
Final presentation: May 2nd, 2pm--4pm, DL480.
Final report Due: May 1st
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).
- Lecture Topics:
- A tentative list of topics is here in [pdf].
Topic 0: Introduction to computational topology. (slides [ppt], [pdf])
Topic 1: Basics (notes [pdf])
Topic 2: Simplicial complexes (notes [pdf])
Topic 3: Simplicial homology, and computation (notes [pdf])
Topic 4: Persistent homology (notes [pdf])
Topic 5: Functions induced persistence (notes [pdf])
- Topic 6: Some applications of topological persistence (slides [pdf])
- Topic 7: Homology inference from points data (slides [pdf])
- Topic 8: Reeb graphs, contour trees, and their applications (slides [pptx])
- Topic 9: Hierarchical clustering trees (slides [pptx])
- Topic 10: Data Denoising (slides [Part 1: pptx], and [Part 2: pdf])
- Topic 11: Mapper and Multiscale mapper (slides [pdf])
- Software / Tools resources:
- Computing Persistent homology:
- 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.
- 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.
- Compute persistence for simplicial maps:
- Reeb graph / contour tree related:
- The randomized algorithmm for computing Reeb graph for arbitrary simplicial complex can be downloaded here.
- The Denali software package for visualizing terrain metaphor is available here. The package includes code to compute contour trees for a scalar field.
- Discrete Morse complex:
- The DisPerse package is available here . The software only takes 2D or 3D volumetric data, or Delaunay triangulations.
- Some of the students final presentation slides can be found here (not a complete list).
- Suggested Readings / Related Resources:
- You can check out the course material by Tamal Dey here for reference.
- A one-page project/survey proposal is due on March 21, to describe briefly your course project / survey (what it is about, and motivation etc). Please send the proposal to me via email.
- The final presentation for your project / survey will happen on May 2nd, 2pm--4pm.
The final report of your project/survey is due on May 1st.