Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Background

I am currently working on the homology of some moduli space and there exists a much simpler chain complex with the same homology. It is a quotient of a bisimplicial complex by a subcomplex. One could say that some faces are degenerate, thus are zero. Unfortunately, it's too hard to compute the homology groups by hand.


Given a free chain complex of finite type over the coefficient ring $\mathbb{Z}$ or $\mathbb{Z}/{p^k}$, with $p$ prime, I cannot compute the homology groups by hand. Some matrices have approximately $18.000.000 \times 15.000.000$ entries.

Question: Is there a C/C++ library or an external program that does the following (in descending order of importance)?

  1. computes the homology groups of the given chain complex
  2. describes the image of one or multiple cycles as a linear combination of homology classes
  3. is efficient (e.g. it is capable of using multiple CPUs)
share|improve this question
3  
18MM by 15MM entries general matrix is out of reach for Smith normal form algorithms (they are generally super-cubic), so I would advise simplifying the problem first. –  Igor Rivin Sep 12 '12 at 16:36
    
How is your input presented: is there a simplicial decomposition, or do you just have an arbitrary collection of boundary matrices over the coefficient ring? –  Vidit Nanda Sep 14 '12 at 20:49

3 Answers 3

There are several applications and libraries out there that deal with homology computations with various approaches to the computation. One field with a strong focus on efficient computation of homology is persistent homology; which computes classical homology as a side-effect.

For C/C++ use, I would recommend you take a look at Dionysus (http://mrzv.org/software/dionysus/). This library is optimized for computing persistent homology with field coefficients; and is one of the most capable libraries I know of in this field.

As for your wishlist, I would point out that from the persistent homology side, integer coefficients are Just Not Done; small prime field coefficients gets you some of the information contained in integer coefficients, but with a huge gain in computation speed. Computing groups and producing a basis for the homology is done by most systems around; but parallelization is yet basically unsolved.

Of course, you want classical homology, not persistent and you want integer coefficients. I would recommend you spend some time looking around for the field of Smith normal form computation libraries and roll your own from there. There is some interesting research into efficient and parallelizable Smith normal form computation; both Kaltofen and Jäger seem to have papers on the subject, and they could well have implementations you can use.

share|improve this answer
1  
I would add that the case of $\mathbb{Z}/2\mathbb{Z}$ in particular is most convenient computationally, and is covered in great detail in Edelsbrunner and Harer or Zomorodian. –  Steve Huntsman Sep 12 '12 at 11:08
    
Since the example in question comes from the cohomology of a moduli space, I suspect that $H^{\ast}(X, \mathbb{Z})$ does not have a lot of torsion. By computing cohomology with $\mathbb{Z}/p$ coefficients for several different large $p$, and staring at the universal coefficient theorem, you might be able to make an intelligent guess as to what the torsion free part of $H^{\ast}(X, \mathbb{Z})$ is. –  David Speyer Sep 12 '12 at 13:00
    
Can Dionysus handle 15 million dimensional chain complexes? –  Ryan Budney Sep 12 '12 at 17:15
    
I know Dionysus can deal with several million, not sure where the upper limit resides. In particular, the upper limit probably depends a lot on what size computer you have access. –  Mikael Vejdemo-Johansson Sep 15 '12 at 6:20
    
Dionysus also has python bindings. –  Anthony Bak Sep 16 '12 at 19:34

I realize that this is an old question and it is likely that the OP has moved on, but let me summarize the state-of-the-art as it exists now.


The given sizes (18 million by 15 million) are pretty hopeless if you are planning to resort to matrix methods. To put things in perspective, latest version of Linbox has been chugging away at a 12,000 x 11,000 dense integer matrix on my cluster for over three months with no end in sight. So, you would almost certainly need to resort to a reduction method and the most effective ones are based on discrete Morse theory.

Since discrete Morse theory exploits the presence of units in the boundary matrix, it is important to keep in mind that there is a world of difference computationally between computing with $\mathbb{Z}$ coefficients versus computing over a field. Over a field, there is no trouble since everything nonzero is a unit, and you are guaranteed to be able to Morse-reduce very effectively.

If you are working over the integers, then everything depends on whether your matrix has many units (i.e., 1's and -1's) in it. If you are unit-rich, and if the actual homology of your complex is light on torsion, then there is a pretty good chance that the Morse-reductions will be drastic even over the integers; and they might produce much smaller boundary matrices which can then be fed into Linbox.

I've written some C++ software to implement these discrete Morse theoretic reductions before computing homology (over the integers!): see here. Although it doesn't mention this explicitly on the website, you can easily feed the software various matrix representations of boundary operators (rather than simplicial complexes) and produce smaller matrices which fit into a quasi-isomorphic chain complex.

share|improve this answer

The Homology package for GAP (by Dumas, Heckenbach, Saunders, and Welker) doesn't sound exactly like what you want, as it focuses on simplicial homology, but the techniques it uses might be helpful for you to look at.

It uses the LinBox C++ libraries for handling the linear algebra, and this might be useful in rolling your own. Available at http://www.linalg.org .

share|improve this answer
    
The LinBox routine for finding the rank of a matrix is quite efficient. Still, the OP's matrices are probably out of reach in terms of their size. –  Jim Conant Sep 13 '12 at 1:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.