ICMS 2014: Session on “Software for Computational Topology”

The 4th International Congress on Mathematical Software (ICMS 2014) takes place in Seoul, Korea on Aug 5-9. This year, it will host a workshop session dedicated to Computational Topology. Contributions on state-of-the-art software for topological problems as well as applications of such software to other domains are welcome. See the dedicated webpage for more information,

How to contribute: Submit a short abstract of 200-500 words to the session organizer until March 31. You will get a notification about acceptance within one week and upon positive evaluation, you will give a talk at ICMS. An extended abstract (due end of April) will appear in the conference proceedings.  A special issue of Journal of Symbolic Computation will be organized immediately after the workshop.

ATMCS 6 open for registration

Dear ALGTOP-L,

Algebraic Topology- Methods, Computation and Science 6 (ATMCS6) is now open for registration. The conference takes place at PIMS University of British Columbia May 26-30.

Confirmed speakers include:

Amit Patel
Donald Sheehy
Jeff Erickson
Jose Perea
Liz Munch
Michael Robinson
Omer Bobrowski
Peter Bubenik
Radmilla Sazdanovic
Sayan Mukerjhee
Vanessa Robbins
Yuliy Baryshnikov
Tamal Dey
Shmuel Weinberger
Raul Rabadan
Chris Hoffman
Vin de Silva

For more details, see:
http://www.pims.math.ca/scientific-event/140526-atmcs

Applied and computational topology refers to the adaptation of topological ideas and techniques to study problems in science and engineering. A particular focus is on using invariants and methods of algebraic topology to understand large high-dimensional data sets. The further development of topological techniques for use in applications and the creation of new areas of application in the subject are amongst the goals of this workshop.

The workshop will bring together leading researchers in this emerging discipline as well as providing an opportunity for young mathematicians to get involved in it. In past years, the ATMCS conference has been very successful in providing a forum for cutting-edge research to be disseminated; attendance tends to represent a broad swath of the diverse research community which works in this area.

Workshop Format:
The workshop will feature lectures and discussion in the morning and afteroon. Mid-Morning and Afternoon refreshments will be provided during the conference.

On behalf of the organizers
Andrew Blumberg, U Texas
Matthew Kahle, Ohio State
Mikael Vejdemo-Johansson, KTH / IMA / IJS

Source material for Topological Data Analysis

To start off the feature articles at appliedtopology.org, I figured it might be worth while collecting good entry points to the field. One of the most common questions I get about persistent homology and topological data analysis is how to get started with our techniques and ideas.

Overview articles and books

First off in the list of entry points is the written word. There are survey articles, overview articles and books written about topological data analysis as a whole, as well as focusing on specific parts.

Topology and Data by Gunnar Carlsson. This survey article came soon after Ghrist’s survey, and covers persistent homology, as well as Mapper for topological simplification and modeling. It also comes with a good discussion of the underlying philosophy of the field.
Start here.

Barcodes: the persistent topology of data by Robert Ghrist. This is the first major survey article to come out, and covers persistent homology and some of its applications.

Topology for computing by Afra Zomorodian. This is the first book format exposition of persistent homology for applied and computational topology. It is a good and self-contained introduction to the field, if ever so slightly dated: in particular, it does not cover anything about zigzag persistence or multi-dimensional persistence.

Computational Topology: an introduction by Herbert Edelsbrunner and John Harer. This book covers the state of the art as of 2010 of computational topology, with some focus on persistent homology: one third of the book is devoted to persistence and its applications. Throughout, the book discusses the underlying theory, the most obvious algorithm, and the fastest known algorithm.

Software packages

So you understand what the underlying ideas of the field are. Next up, you’ll want to try them out on your own data. There are some ways you can go to do this, and they all have their specific strengths and weaknesses.

Plex, jPlex, javaPlex: this sequence of libraries were developed in the Stanford group, and with an explicit aim at always interoperating smoothly and easily with Matlab. Of the three, we currently recommend javaPlex unless this library does not cover your exact use case — in which case some methods may exist in jPlex. Plex is written in C++, and connects to Matlab through a MEX interface, while jPlex and javaPlex are both Java libraries.

Dionysus: this library, written and maintained by Dmitriy Morozov, provides a platform for developing and experimenting with computational topology algorithms in C++ or in Python. It interfaces with CGAL for low dimensional geometric constructions, and has example applications provided for persistent homology, cohomology, vineyards, alphashapes and numerous other common techniques.

Perseus: this package, developed by Vidit Nanda, provides a platform for computing persistent homology for cubical and simplicial complexes generated in a number of different ways. It specifically uses methods based on discrete morse theory for speeding up computations.

pHat: this package, created by Ulrich Bauer, Michael Kerber and Jan Reininghaus builds on results by the authors that speeds up persistence computation by specific tricks that use structures in a persistence boundary matrix. Currently only using Z/2-coefficients and not constructing the complex for you, it seems to be the fastest publicly available package.

CHomP: this software package came out of the CHomP research project, and consists of a rich collection of tools to work persistently or statically with cubical complex data. For homology on image or voxel collection data, CHomP forms the fastest and most complete analysis system available right now.

We warmly appreciate suggestions for more papers, software, or other resources if you have anything to add to this list.

Move of the site

After over a year of mostly inactivity, we have moved platform: away from Gandi.net and to a WebFaction-based server. Kudos to Ryan Lewis for taking over hosting.

In addition to Mikael and Ryan, we would like to invite more members of the community to help build up appliedtopology.org to a good gathering point for the community of applied and computational topology. If you want to help out, or have opinions on what should be done, drop us an email at admin@appliedtopology.org and we’ll work it all out.

Speeding up Homology via Duality?

In the last post I constructed for any (locally finite) simplicial complex a dual complex. Today, I thought of using this to gain a potential speed-up in computational homology. Note that simplicial homology of is the same as Cech homology of the cover given by open stars of the vertices of . This is because … Continue reading

In the last post I constructed for any (locally finite) simplicial complex K a dual complex. Today, I thought of using this to gain a potential speed-up in computational homology.

Note that simplicial homology of K is the same as Cech homology of the cover given by open stars of the vertices of K. This is because the nerve of this cover is precisely K and Cech homology is not-so-secretly the simplicial homology of the nerve.

However, we know that the dual complex has the same homotopy type as K, but the number of vertices in the dual complex is equal to the number of maximal simplices. Simplicial homology of this dual complex is the same as Cech homology of the cover given by the closed top dimensional cells in K.

Here is a case where this observation results in a most dramatic speed-up. The standard n-simplex \Delta^n has 2^{n+1} simplices and naively simplicial homology requires storing all of these. However, the dual complex is a single point and Cech homology here reveals that. Thus we have gone from a chain complex with n+1 chain groups, each of which are dimension \binom{n+1}{j} to a chain complex concentrated in a single degree, all by using this duality.

Of course, the case of graphs shows where this duality fails miserably. The dual complex creates simplices whose dimension corresponds to the degree of vertices in the original graph, so we can go from a two-term chain complex with a single boundary matrix, to arbitrarily large chain complexes.

This presents a question of possible interest: For what simplicial complexes does the dual complex and the original complex have the same number of simplices? Triangulated manifolds clearly do, but what about other simplicial complexes? Can we say something about the expected discrepancy of these numbers?

Dual Simplicial Complexes

In the process of designing homework problems for Applied Algebraic Topology (ESE 680-003) last night, I stumbled upon a most beautiful application of the nerve theorem as well as a construction of a dual simplicial complex that is defined for any (locally finite) simplicial complex . This dual complex has the property that it is … Continue reading

In the process of designing homework problems for Applied Algebraic Topology (ESE 680-003) last night, I stumbled upon a most beautiful application of the nerve theorem as well as a construction of a dual simplicial complex that is defined for any (locally finite) simplicial complex K. This dual complex has the property that it is always homotopic to the original simplicial complex.

Let K be a simplicial complex with vertex set V. The open star U_v of a vertex v is defined to be the set of simplices \sigma containing v.  Visibly, the nerve of the cover \mathcal{U}=\{U_v | v\in V\} is the same as the simplicial complex K.

On the other hand, one can consider a different cover by closed sets, or dually Alexandrov opens when one reverses the partial order. Define a simplex to be maximal if it is not the face of any other simplex. Define the closure \overline{\sigma} of a simplex \sigma to be the set of faces of \sigma, written \tau\leq\sigma, so that \sigma\leq\sigma, i.e. \sigma is a face of itself.

Now define the dual simplicial complex of K to be the nerve of the cover \mathcal{V}=\{\overline{\sigma} | \sigma \,\mathrm{maximal}\,\}.

The nerve theorem works for convex closed sets or open sets with contractible intersections, so we know this dual simplicial complex has to be homotopy equivalent to the simplicial complex K.

If we use Graeme Segal’s construction of the classifying space of the cover category X_U (sometimes called the Mayer-Vietoris blowup complex) in the paper “Classifying Spaces and Spectral Sequences” then we should be able to construct a similar dual space for cell complexes by looking at the open stars of vertices and the closures of maximal cells respectively.