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.



Algorithm that decreases the size of the simplicial triangulation
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](http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/Publications/DHSW.pdf), 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](http://chomp.rutgers.edu/); 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](http://www.math.tu-berlin.de/diskregeom/stellar/additional_publications.html) and [link to the software](http://www.math.tu-berlin.de/diskregeom/stellar/software.html)). I don't think it's intended for use in real time, though.


