Blog: Articles from June 2010

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.

For reasons beyond my ken, I cannot sign into AIM at the moment I‘m writing this. This lapse in stimulus caused my brain to seek more meaningless information bombardment before it collapsed into a pile of quivering, atrophied jelly. That’s right: I went on Facebook. And as I sat here, staring at the New Feed on the homepage, I sighed.

The News Feed is useless for my purposes, as are many of the tools Facebook purports to offer me.

Now, although I have been (and continue to be) critical of Facebook’s privacy policies, I did not quit Facebook and have no plans to do so. Despite my forthcoming complaints, Facebook is a useful tool in some respects; managed properly, privacy is a concern but not enough motivation for quitting the service altogether.

My experience with Facebook has had incredible highs and some lows. Facebook reunited me with some friends, with whom I lost touch after moving across town, from elementary school. They are now friends in this newfangled adulthood thing I‘m trying on for size. On the other hand, I’ve accepted friend requests from people I barely knew in high school (or barely remember from elementary school), purely because I felt bad saying “no.” I try to be more selective now, but the damage is done.

So I was happy when Facebook introduced the ability to make lists of Friends. I am nowhere near as compulsive nor as organized as some people I like to know. I lack the determination and the single-minded intensity to manifest a vortex of order around myself. Yet I do, when the fancy strikes me, like to put my digital life into lists. Friend lists offered me the opportunity to sort people by how I knew them, and by who I cared about the most.

There was also a nifty feature that let me filter the news feed by friend list. Suddenly instead of seeing the inane status of someone with whom I’ve barely interacted, either in person or online, I was able to tune out the noise and only see what really mattered to me. It was quite … useful.

Several redesigns later, and that feature is, while not entirely gone, much less conveniently employed. It’s still possible to do what I want, but I can’t find a way to make it the default option (tips on this, if it’s possible, would be much appreciated). So by default, the news feed shows me updates from all of my friends and from pages that I’ve “liked” but from which I don’t want to see updates. The “options” the news feed offers me are limited; I can choose to emphasize some friends and hide others, but that doesn’t seem very helpful. And it is hard enough to access the options dialog, because the link is at the bottom of the page … which keeps on loading more status updates every time I scroll down!

I know that picking on the Big Bad Facebook Monster is the new pink, and I‘m loath to jump on the bandwagon. Nevertheless, my AIM-lessness and idle navigation to the Facebook news feed provoked in me a desire to express my frustration that such a potentially useful feature has been rendered anaemic and useless by poor design.

As it is, I don’t use Facebook for the applications. I don’t use much for photos, or for its news feed. I’m still on Facebook because it’s a useful communications medium, a way to contact my friends and keep in touch. Yet as far as websites go, Facebook’s design is deeply flawed—and their numerous redesigns seem to indicate they sense this, even as each one compounds the problem.

Yes, yes, I know. At this rate, my weekly recap will become bi-weekly. I didn’t do a lot the week before last, owing to Victoria Day making for a shortened week. So rather than two very short blog posts, I decided to forbear and write one short blog post instead.

The last two weeks have been more reading, more learning, and a little thinking. I hesitate to ascribe a label like “productive,” since it’s hard to quantify. I think I understand my problem now, but there remains a lot for me to learn in order to start trying solutions.

I tried running the original algorithm for computing the spreading number, which was written in CoCoA, on my computer. I had hoped that my 2 GB of RAM and 1.83 GHz processor would have enough memory to compute some additional numbers. Alas, CoCoA stubbornly crashed (after several long hours) each time I instructed it to do so.

So I ported the code to Macaulay2. It’s even slower, which makes me suspicious that I’m missing something—after all, I am learning both languages, so I‘m sure that in transliterating the code I managed to miss an obvious way to make it more efficient. Still, it looks like the original algorithm won’t produce many more useful results, at least not until I stick it on SHARCNET.

My supervising prof pointed me to a series of lectures he gave on combinatoric commutative algebra. Last week I started working through those, and I’ll continue doing so this week. He’s given me several promising “leads,” I suppose you‘d call them, but at this point, I have to start exploring avenues of interest and seeing if they produce any interesting results. I’ve already toyed with some alternative approaches in Macaulay2, familiarizing myself more with the language, but I think I need more experience with the mathematics first.

Probably the most significant news of the past two weeks would be my decision to attend the Canadian Undergraduate Mathematics Conference at the University of Waterloo and the Combinatorics & Optimization Summer School preceding it. Initially I was reluctant to go, because I don’t like to travel, but Aaron and (maybe) Rachael are going, so I won’t be alone. Plus, I’ll get to visit my grandparents. That’s July 5-10, a few more weeks away. Until then … time for more learning.