The Beginning of Research

Six days ago school started. Fourth period that Tuesday I walked in to the Computer Systems Lab to see all of the projects we had proposed last year projected on the wall. at that point, I did not know what I really wanted to do, but knew that it was not what was on the wall. I did, however, know that I wanted to do something related to math, but because I'm in a computer systems lab, I would have to relate it to computing somehow. So that day I told the teacher that I had changed my mind about what I wanted to do over the summer and that I would do some sort of computational mathematics, but I didn't know what.

So that evening I started googling. What sorts of topics could I do computationally? My first thought was group theory, and indeed a google search for computational group theory yielded results, but I quickly realized that I did not know the important questions in group theory and would be more or less at a loss for what I could actually make progress on. As a next thought, I thought about what I could do that I knew a little bit about but not much, so while doing my research on something that I know about, I could be learning some interesting tidbits about the topic at hand. My topic of choice was topology.

Now I had learned some topology at Mathcamp, but of course a couple weeks isn't enough to say that I really know topology. I had some background in homotopy theory as well, as JR had gone through and shown us several nice applications of the fundamental group, and on the last day had briefly gone over the skeletal concepts behind homology. So if I were going to do a topological project, I would need to determine a few things:

1) How am I going to represent a topological space? Practically all interesting spaces have an infinite number of points (although maybe there is something interesting computationally in enumerating the finite spaces as there is for finite groups - I haven't looked into it), so there needs to be some implicit form.
2) What am I going to compute? I had some idea that homology was much easier to compute than homotopy (and that higher homotopy groups were often computed via what I later found out is called the Hurewicz Theorem), but since I really didn't know what homology was I wasn't sure how much I could do with this and the only homology I had seen was simplicial homology, and I wasn't sure about it's applicability.

So in order to answer these questions I started searching computational topology. What I quickly found was the Computational Homology Project (CHomP) and I also found references to this program called Kenzo. After reading through the documentation on the Kenzo site and the CHomP site, I realized that most of it was beyond what I could learn in a reasonable amount of time. So I abandoned this line of thought and went to a backup: complexity.

The biggest impression that I got from reading about CHomP and Kenzo was that their algorithms sucked. I had no idea what their algorithms really were, I couldn't find any satisfactory descriptions, but I knew that they took a long time, although much faster than humans (Kenzo claims to have experimentally determined homology groups that no human has). So I thought what is the most basic question that I can study the complexity for? My decision solved the first issue above - the formatting of the space. I said, "Okay, I know the definition (at least) of Simplicial Homology, so let's see how fast Simplicial homology can be computed theoretically."

That search yielded fruitful results. The first paper I found was titled On the Complexity of Computing the Homology Type of a Triangulation. Reading through this paper I found that this was pretty much exactly what I was looking at. The authors took a finite simplicial complex in matrix form (each column of the matrix simply being the boundary of the corresponding simplex) and probabilistically computed the homology groups in O(Dn^2) time where D is the dimension of the complex and n is the number of simplices. So this was a great start. Even better was at the end the authors wrote that area for future research could include probabilistic computation of homology for regular cell complexes and CW complexes, which are not conceptually much trickier than simplicial complexes. They also say that the computation of the cohomology ring operations could be useful, since while the cohomology is determined by the homology, there are spaces with the same homology and cohomology with different ring operations. So these two areas are where I am looking toward for my research. Currently I have only actually read into the first. I don't actually yet know what they are referring to by the cohomology ring operations.

So now I have a topic, but I need a plan of attack. While reading this first paper and thinking about it a little in my head, this problem of computing homology groups is really about computing something from an integer matrix, since the boundary maps can each be simply represented as an integer matrix. What I had gathered was that this was called Smith Normal Form, but I couldn't really understand what Smith Normal Form was, why it existed, or how to compute it naively. This was what I looked for today, and found this rather readable paper that introduces the concept of Smith Normal Form and explains how to compute it in a finite amount of time (although not bounded by anything, since the fact that it's finite simply comes from the fact that the integers are Noetherian). So now I have at least a plan for the first part of my research. I can for now remove myself from the topological nature of my problem and attack a very simple problem of computing Smith Normal Form. The topology will come back in because the fact that the matrix represents a simplicial (or regular cell or CW) complex means that it may be forced to satisfy certain sparsity or regularity requirements, which (as in the paper linked in the preceding paragraph) can be exploited in order to obtain a much faster expected running time than the naive or even less naive deterministic algorithms.

This series of posts will probably run two or three times a week, but most of the posts won't be this long as I was covering essentially an entire week here.