16
$\begingroup$

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)
Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Sep 12, 2012 at 16:36
  • $\begingroup$ 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? $\endgroup$
    – Vidit Nanda
    Commented Sep 14, 2012 at 20:49

3 Answers 3

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steve Huntsman
    Commented Sep 12, 2012 at 11:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Sep 12, 2012 at 13:00
  • $\begingroup$ Can Dionysus handle 15 million dimensional chain complexes? $\endgroup$
    – Ryan Budney
    Commented Sep 12, 2012 at 17:15
  • $\begingroup$ 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. $\endgroup$
    – Mikael Vejdemo-Johansson
    Commented Sep 15, 2012 at 6:20
  • $\begingroup$ Dionysus also has python bindings. $\endgroup$
    – Anthony Bak
    Commented Sep 16, 2012 at 19:34
11
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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 .

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Jim Conant
    Commented Sep 13, 2012 at 1:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .