Abubakr Muhammad

Postdoctoral Research Fellow, jointly with
Quantum Information Processing Group, and
Center for Intelligent Machines

School of Computer Science, McGill University, Montreal, Canada

Up

Computational Topology in Science & Engineering

Reading Group, Winter 2008

Organizer: Abubakr Muhammad

Time: Wednesdays at 4:15 pm

Venue: McConnell Bldg. Room 321 (SOCS Lounge)  

What is Computational Topology?

In recent years, there has been an enormous interest among researchers in various disciplines to develop and use topological methods for solving various problems in science and engineering. These algorithmic methods provide robust measures for global qualitative features of geometric and combinatorial objects that are relatively insensitive to local details. This makes topological abstractions into useful models for understanding qualitative geometric and combinatorial questions in several settings. The abstract machinery of algebraic topology has been used in various contexts related to data analysis, object recognition, discrete & computational geometry and distributed computing.

Summary of Objectives & Activities

The aim of this reading group is to communicate some of these recent developments to the participants with a minimal background in algebraic topology. Our focus will be on applications, although the proper appreciation of this research will require the understanding of some sophisticated mathematical methods.

 Since it is expected that the attendees will come from diverse backgrounds in science, mathematics and engineering; the organizer will provide tutorials on the required background in topology. Moreover, the organizer will demonstrate how to use various computational topology software tools. The majority of meetings will be dedicated to discussing various research articles written by the leading experts in the field. Hopefully, these activities will enable the participants to generate new mathematics as well as new applications.

Topics

 Mathematics: Homology, homotopy, Morse theory, Conley index theory, configuration spaces

Computational Methods:   Cech-, Rips-, witness- and alpha-complexes, persistent homology of filtrations, harmonic methods for computing homology, software tools

 Applications: Coordination, navigation and reconfiguration in robotics, coverage and routing in sensor networks, visualization and qualitative analysis of high-dimensional data sets, analysis of nonlinear dynamical systems, structural biology, image classification, distributed algorithms

Who should attend?

Mathematicians with interest in topology, geometry and dynamical systems
Computer scientists investigating computational geometry, machine learning, visualization & data analysis
Engineers interested in algorithmic aspects of robotics, networked sensing and control theory
Life scientists dealing with large data sets in molecular biology, neuroscience, systems biology

Tentative Schedule  

DATE TOPICS FRONTIERS SUGGESTED READING

Background

Jan 16 Overview of computational topology . Barcodes: The persistent topology of data by Robert Ghrist.
Jan 23 Simplicial & cubical complexes; homotopy Math Notes on homology theory by Abubakr Muhammad. Also check Afra Zomorodian's course notes. 
Feb06 Homotopy; simplicial homology Math, CS Same as last week.
Feb 13 Filtrations & persistent homology Math, CS Computing Persistent Homology by Zomorodian and Carlsson.
Feb 20 Hands-on training: Plex software package CS
Data Analysis, Learning & Visualization
March 05 Manifold Learning from point cloud data sets (PCD) Math, CS, Bio

Finding the homology of submanifolds with high confidence from random samples by Niyogi, Smale and Weinberger
March 12 Persistence and its Stability in PCDs Math, CS, Bio Persistent Homology - a Survey by Herbert Edelsbrunner and John Harer.
April 02 Natural Image Classification EE, CS, Bio

A Topological Analysis of the Space of Natural Images Gunnar Carlsson and Tigran Ishkhanov.
April 09 Homology computation using harmonic analysis CS, Math Computing Betti numbers via Combinatorial Laplacians by Joel Friedman
 Networks and Sensing
Coverage problems in sensor networks –I EE, CS Homological sensor networks by deSilva and Ghrist (survey). Blind swarms for coverage in 2D by Ghrist, deSilva, Muhammad
Coverage problems in sensor networks –II EE, CS Coordinate-free coverage in sensor networks with controlled boundaries via homology by deSilva and Ghrist.
Landmarks, routing and homology feature size in sensor networks EE, CS Geodesic Delaunay Triangulation and Witness Complex in the Plane by Gao, Guibas, Oudot, and Wang.
Robotics and Coordination
Morse theory – continuous, discrete & combinatorial Math
Navigation in robotics EE, ME, CS
Configuration spaces – I: Distributed coordination Math, ME, EE
Configuration spaces – II: Reconfigurable systems Math, ME, EE
Dynamical Systems
Conley index theory Math
Computer assisted proofs in dynamical systems Math, Phys, Bio
Hands-on training: CHomP software package Math, CS
Miscellaneous Topics
Topology of random data and random fields Math, CS
Protein docking and structural biology Bio, CS

Resources in Computational Algebriac Topology

(If you find someone missing in these lists, please email me!)

Workshops/Programs

2006 MSRI Workshop on Application of Topology in Science and Engineering
2004 IMA Short Course Computational Topology
Topological Methods in Scientific Computing, Statistics and Computer Science, Stanford University
Computational Homology Project, CHomP
DARPA-DSO program in fundamental mathematics: Sensor Topology for Minimal Planning
DARPA-DSO program in fundamental mathematics: Topological Data Analysis
2007 TTI Workshop on Geometric and Topological Approaches to Data Analysis
2008 International Workshop on Algorithmic Topology, Bellairs-McGill
Workshop on Topology learning, NIPS 2007

Courses

Computational topology by Prof Edulsbrunner at Duke
Computational topology and geometry by Prof Yap at NYU
Introduction to computational topology by Prof Zomorodian at Dartmouth
Computational dynamics and topology by Prof Day at William & Mary
Topology for computing by Profs Cheong & Choi at KAIST
Computational topology seminar, by Profs Giesen and Sagraloff, Max Planck Institute

Software

Plex (Stanford)
Computational Homology Project, CHomP

Books

Tomasz Kaczynski, Konstantin Mischaikow, Marian Mrozek (2004), Computational Homology, Springer, ISBN 0-387-40853-3. 
Afra J. Zomorodian (2005). Topology for Computing, Cambridge, ISBN 0-521-83666-2. 
William Brasener (2006), Topology and its applications, John Wiley, ISBN: 978-0-471-68755-9.
Allen Hatcher, Algebraic Topology.