Music must change

I like to joke with my friends about how easy I have it this summer. I‘m sitting in a cozy little office with a fan, proximity to a kettle, and a high-speed Internet connection. Unlike a summer research student in, say, chemistry or biology, I don’t have to manipulate lab equipment or sex fruit flies (Cassie :P). The extent of my experimentation will involve uploading programs to a high-powered computing network and asking it kindly to compute a few more numbers for me. I Google math papers relevant to my problem, try to understand what they say, and see if I can come up with my own ideas. One thing I love about math research, especially in my area of interest, is how much it’s thought. All I really need is a blackboard and chalk, or pencil and paper. (That being said, the high-powered computing network does help when I get to the computation step!)

Of course, it’s not all fun and games (even though I did learn how to solve a Rubik’s cube last week). Maths is hard! And right now, even though I’ve been in university for three years, I feel like an amateur groping around an unsolved problem. I know that research can be like that in general, and I’m still having lots of fun—and learning a lot. Nevertheless, sometimes I feel like a poser. And nothing is worse than a math poser!

I was all excited, two weeks ago, because I had almost finished an algorithm to compute the spreading number recursively. I was tackling the problem as one of finding a maximum independent set. The spreading number is, among other things, the cardinality of the maximum independent set of a certain type of graph. (The covering number is an analogous clique cover cardinality). The general problem of finding a maximum independent set is NP-hard. This means that there likely isn’t a very efficient algorithm for solving the problem (if there were, then P=NP, and that’s way above my pay grade). The best I could hope for was a good algorithm for my specific case; indeed, that was my hope for this algorithm.

After returning from the weekend, I finished the algorithm and happily set Macaulay2 to work, asking it to compute the spreading numbers and compare it with the values we already know. Alas, there were discrepancies, and I quickly understood why: I had made a fundamentally flawed assumption in constructing the algorithm. So while the algorithm did exactly what I wanted it to do, it turns out that what I wanted would not give me the graph’s maximum independent set.

Back to square one!

Frustrated but not very surprised am I. The problem is non-trivial, so I did not really expect such a simple solution. And I have plenty of summer left in which to try new ideas. Right now I am looking at Hilbert series. Most computer algebra systems, including Macaulay2, use Hilbert series to compute the dimension of rings (and this is how my professor’s orginal algorithm computes the spreading number). For larger rings, this computation takes up too much memory.

The easiest solution is, of course, to throw more memory at the problem. We had hoped my computer would be able to compute at least another two or three of the numbers, but this was not to be. Even without any refinements to the algorithm, however, SHARCNET should blow my computer out of the water. This week, I am looking at ways of breaking the computation of the Hilbert series into independent tasks so I can make use of throughput computing.

Oh, and I did learn how to solve a Rubik’s cube. I obtained one in my young adolescent days, but because I have poor spatial skills, I was never able to solve it on my own. Last week I observed Rachael manipulating her cube like a pro. I expressed my admiration and awe, and she just shrugged and mentioned that it was a matter of using certain algorithms (which makes sense). I was doubtful of my ability to learn the necessary algorithms; fortunately, I think I understand enough now to solve the cube reliably. I doubt I’ll ever be a speedcuber, but that is one puzzle down.

Now back to my shiny infinite polynomial series.