Computer aided homology computations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T20:52:07Z http://mathoverflow.net/feeds/question/106985 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106985/computer-aided-homology-computations Computer aided homology computations Felix Boes 2012-09-12T08:11:47Z 2012-09-18T07:20:21Z <h2>Background</h2> <p>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.</p> <hr> <p>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:</p> <ul> <li>computes the homology groups</li> <li>describes the image of one or multiple cycles as linear combination of homology classes</li> <li>is efficient ( e.g. it is caplable of using multiple CPUs )</li> </ul> <p>(descending order of importance)</p> http://mathoverflow.net/questions/106985/computer-aided-homology-computations/106993#106993 Answer by Mikael Vejdemo-Johansson for Computer aided homology computations Mikael Vejdemo-Johansson 2012-09-12T09:22:43Z 2012-09-12T09:22:43Z <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/106985/computer-aided-homology-computations/107026#107026 Answer by Russ Woodroofe for Computer aided homology computations Russ Woodroofe 2012-09-12T16:31:11Z 2012-09-12T16:31:11Z <p>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.</p> <p>It uses the LinBox C++ libraries for handling the linear algebra, and this might be useful in rolling your own. Available at <a href="http://www.linalg.org" rel="nofollow">http://www.linalg.org</a> .</p>