Computational techniques in graph homology of the moduli space of curves

The object of this thesis is the automated computation of the rational (co)homology of the moduli spaces of smooth marked Riemann surfaces Mg;n. This is achieved by using a computer to generate a chain complex, known in advance to have the same homology as Mg;n, and explicitly spell out the boundary operators in matrix form. As an application, we compute the Betti numbers of some moduli spaces Mg;n. Our original contribution is twofold. In Chapter 3, we develop algorithms for the enumeration of fatgraphs and their automorphisms, and the computation of the homology of the chain complex formed by fatgraphs of a given genus g and number of boundary components n. In Chapter 4, we describe a new practical parallel algorithm for performing Gaussian elimination on arbitrary matrices with exact computations: projections indicate that the size of the matrices involved in the Betti number computation can easily exceed the computational power of a single computer, so it is necessary to distribute the work over several processing units. Experimental results prove that our algorithm is in practice faster than freely available exact linear algebra codes. An effective implementation of the fatgraph algorithms presented here is available at http://code.google.com/p/fatghol. It has so far been used to compute the Betti numbers of Mg;n for (2g + n) 6 6. The Gaussian elimination code is likewise publicly available as open-source software from http://code.google.com/p/rheinfall.