Algorithm that decreases the size of the simplicial triangulation

Hello!

Let X be a topological space. We are considering only abstract simplicial complexes, i.e. a finite list of finite lists of integers. Is there any algorithm (more or less efficient?), that would for a given triangulation of X produce another SMALLER simplicial complex, that is also homeomorphic to X?

My main need for such an algorithm is coming from the desire to implement a more efficient algorithm for computing homology of a space.

The algorithm doesn't need to produce a minimal triangulation (not at all), but it has to be fast enough that it can be used in my homology program (faster than the integer smith normal form algorithm).

Currently, the f vector of my triangulation of e.g. the 4-torus is {81, 1215, 4050, 4860, 1944}, and of the 5-torus is {243, 7533, 43740, 94770, 87480, 29160}, which is ridiculously large (I used the staircase triangulation of the product to construct torii). So there is a great need to decrease size of the triangulation without losing topological information.

I have searched the literature and ended up empty handed...

P.S. code in Mathematica would be ideal, but I'd be happy with (pseudo)code of any sort.

• Pachner moves would be a start. But removing the simplicial restriction would be a much bigger gain. There are semi-simplicial triangulations of the n-torus with relatively few simplices. – Ryan Budney Feb 7 '11 at 16:08
• The rest also assumes to work in the world of semisimplciial tringulations. Furthermore it might be nice to allow moves, that also change the homeomorphism type but not the homotopy type. or even weaker, that do not change the homology groups. Then my first idea would be to collapse egdes, if this collapse doens't change the homology type (i.e. the obvious projection should be a homology equivalence). I hope that this property is "local", so to check whether a edge is collapsable, one just has to look at a small environment around that edge. – HenrikRüping Feb 7 '11 at 16:41
• In addition to collapsing simplices, you can try to look for a contractible (or acyclic) subcomplex and compute homology relative to that. If the subcomplex is large, then the matrices representing the relative boundary maps will be very sparse. – John Palmieri Feb 7 '11 at 19:55
• Discrete Morse theory is something you might want to look into. This is a nice combinatorial method for collapsing away simplices without changing the homotopy type. I would suggest looking at papers of Robin Forman and Patricia Hersh, for example. – Dan Ramras Feb 7 '11 at 20:56
• Hmm, yes, finding different non-homeomorphic but homologically equivalent triangulations indeed sounds the appropriate way to do it. I'll check out your suggestions in the future. I'm guessing this emis.de/journals/SLC/wpapers/s48forman.pdf or this arxiv.org/PS_cache/math/pdf/9911/9911256v1.pdf would be the place to start. Thanks. – Leon Feb 8 '11 at 6:29

2 Answers

There are a number of papers out there for efficient computation of homology of simplicial complexes; I enjoyed reading this paper by Dumas, Heckenbach, Saunders and Welker, but I don't know how authoritative it is. In particular, though, it seems to help considerably if you have a Smith normal form algorithm tuned to the sorts of matrices which arise as boundary maps of simplicial complexes.

For actual computations of homology groups of simplicial complexes, I would suggest using software from CHomP; it's pretty fast in my experience, much faster than code which just uses a generic Smith normal form algorithm.

If you're willing to stray outside of simplicial complexes, you could use $\Delta$-complexes or cubical complexes (which behave well when dealing with products) or prodsimplicial complexes. I don't know of any software package which deal with prodsimplicial complexes, but you could always write one! Sage handles simplicial, $\Delta$-, and cubical complexes, farming the work out to CHomP if you have it installed.

Finally, if you really want algorithms for making simplicial complexes smaller, you could use the bistellar flip algorithm due to Bjorner and Lutz (see list of Lutz's publications and link to the software). I don't think it's intended for use in real time, though.

• If you're willing to use C/C++ with arbitrary-precision integers, check out the procedure "metricalSmithNormalForm" in Regina: regina.sourceforge.net Click on the links to get to the subversion repository, and look in maths/matrixops.h This is fairly well tuned to computing homology of simplicial complexes but I'd be curious to know if there are substantial further efficiencies available. – Ryan Budney Feb 7 '11 at 19:59
• I should add, if you look at the code, I include references to various papers in the literature where the key ideas were taken from. – Ryan Budney Feb 7 '11 at 20:01

In various respects, the premise of the question is not really correct.

First, you should not think that there is "the" Smith normal form algorithm. There are various algorithms to compute Smith normal form, and what you want in this case is a sparse algorithm. One sparse strategy to compute the Smith normal form (but not the only possible one) looks to simplify the matrix while keeping it as sparse as possible. There is no particular reason that simplifying a triangulation would go better than simplifying these matrices.

Second, it is a theorem that there does not exist any reasonable algorithm to simplify all complicated triangulations of manifolds of dimension $n \ge 4$. It's uncomputable; it's equivalent to the halting problem.

Third, as Ryan points out, you should consider generalized triangulations that consist of simplices glued arbitrarily along their faces. That is a much better choice than simplicial complexes. Then the staircase triangulation of the $n$-torus has $n!$ simplices. This is not great, because it grows factorially. But note that the actual homology groups grow exponentially.

• I find the implementation of Smith Normal Form makes a huge difference. If you're not careful about how you do your row reductions, computing the SNF of a 200x200 integer matrix coming from a simplicial chain complex can easily produce matrices with entries that require thousands of digits to express. But if your code is a little careful about how it chooses its row reductions, the SNF is almost instantaneous, and matrix entries through the algorithm frequently never get larger than one digit. – Ryan Budney Feb 7 '11 at 18:12