6

2

Background

I am currently working on the homology of some modulispace and there exists a much simpler chaincomplex with the same homology. It is a quotient of a bisimplicial complex by a subcomplex. One could say, that some faces are degenrated, thus are zero. Unfortunatly its to hard to compute the homology groups by hand.

Given a free chaincomplex of finite type over the coefficientring $\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. Is there a C/C++ library or an external programm that:

  • computes the homology groups
  • describes the image of one or multiple cycles as linear combination of homology classes
  • is efficient ( e.g. it is caplable of using multiple CPUs )

(descending order of importance)

flag
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 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 at 20:49

2 Answers

6

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.

link|flag
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 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 at 13:00
Can Dionysus handle 15 million dimensional chain complexes? – Ryan Budney Sep 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 at 6:20
Dionysus also has python bindings. – Anthony Bak Sep 16 at 19:34
5

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 .

link|flag
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 at 1:02

Your Answer

Get an OpenID
or

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