Computing homology of very large posets I'm studying the homology of a couple of very large posets (one has over 4 million vertices, though the dimension is only 3).  I want to show the posets are spherical (homology vanishes except in top dimension) or better Cohen-Macaulay.  Because of the size, a direct computation of homology seems impossible, even with a clever program like Simplicial Homology for GAP.
Does anyone know of an algorithm for this sort of thing which could make life easier?  I have tried to find an explicit recursive atom ordering already, but haven't found one.
 A: I've found that discrete Morse theory is very helpful in this context. Here's a link to a nice article by Forman. If you can define a good discrete vector field, it's often possible to drastically reduce the size of the chain complex. The art of course is in coming up with the right vector field.
A: I agree with Jim Conant, discrete Morse theory should help. Acyclic matching of (the Hasse diagram of) the poset is a good candidate for a discrete vector field (see D. Kozlov's book Combinatorial Algebraic Topology, chapter 11). 
However, it does not guarantee that one will get a minimal complex (all the cells are homology cells). If your posets are not "nice" enough then finding a (perfect) acyclic matching will be as hard as finding a recursive (co)atom ordering.
A: You wrote that upper intervals are very nice (i.e., shellable, hence spherical) in your poset, you can try to apply this slightly stronger version of Quillen's Fiber Lemma (compare [Q78, Proposition 7.6] and [AS92, (4.3)]):
Let $f: X \to Y$ be a (monotone) map of posets such that the fibers $|\{f \le y\}|$ are $n$-connected for all $y \in Y$. Then $f$ is $(n+1)$-connected, i.e., for all $x \in X$
 the induced maps
$$f_{x, i}: \pi_i(|X|, x) \to \pi_i(|Y|, f(x))$$
of homotopy groups are isomorphisms for $i \le n$ and epimorphisms for $i = n+1$.
For $Y$ you take the dual of your poset and for $X$ the dual of the poset without the atoms. If you understand the homology of $|X|$ very well, maybe you are able to show that $f$ is null-homotopic, which implies that $|X|$ is $n$-connected and $|Y|$ is $(n+1)$-connected.
[AS92] M. Aschbacher, Y. Segev: Locally connected simplicial maps, Israel Journal of Mathematics 77 (1992), 283-303.
[Q78] D. Quillen: Homotopy properties of the poset of nontrivial p-subgroups of a group, Advances in Mathematics 28 (1978), 102-28.
A: Short note for similar problems.
We solved the problem using RedHom software in 2012, 3 days of computations, ~400GB of RAM.
However, now we have better methods and we can check Cohen-Macaulay property of the huge complex in 30 minutes, 340GB of RAM, using 64-cores Intel E7-8837@2.6GHz (assuming hdf5 input file format). It is so fast, because in parallel we can build a data structure for the complex and compute an optimal discrete Morse vector field.
A: Although Justin already knows this, let me leave a note here.
There are people working on computer programs that aim to compute homology fast, like the group working on RedHom. They reduce the given complex (mostly using variants of discrete Morse theory) before the actual computations take place.
However, as far as I know no reduction methods suited to posets have been implemented in RedHom, so one has to turn the poset into a simplicial complex before performing the reductions. Perhaps the ideas of Barmak and Minian concerning finite topological spaces could be used for performing reductions on the poset level? (Just an idea.)
