Graduation Time: MIT PhD Thesis uses cheap supercomputer

All at Once Computing
.........|....................|..................|..................|..................|

.........|....................|..................|


Dr. Andrew Sutherland will be awarded his Ph.D. degree at MIT on 7 June 2007. He needed a supercomputer to complete thesis thesis and his approach was to link eight HP a6030m dual processor AMD systems together to parallel process new mathematical techniques that will be useful for encryption. Breaking through a previous unsolved problem required developing algorithms that ran thousands of times faster than previous approachs. A calculation that required 15 days on a Sun Sparcstation4 now takes less than 3 seconds on a PC.

I bought one of these inexpensive HP systems to test it out and is extremely fast, almost totally silent, and produces almost no heat compared to the Dell dual processor Intel system sitting next to it. I can see why Dell is "feeling the heat" from the competition. Suffice to say, this HP is blazingly fast compared to my watercooled IBM Thinkpad T42 which I have relegated to the dustbin of computing history. I'm thinking about buying a couple more of the HP systems. For the orginal price of my Dell workstation, I could have a eight system supercomputer lab.

For those of you who are math geeks, here is the thesis abstract:

Order Computations in Generic Groups
by Andrew V. Sutherland
Submitted to the Department of Mathematics on May 16, 2007, in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY
For PDF of thesis click here.

Abstract

We consider the problem of computing the order of an element in a generic group. This is known to require exponential time. The two standard algorithms, Pollard’s rho method and Shanks’ baby-steps giant-steps technique, both use Θ (N^1/2) group operations to compute |?| = N, and a lower bound of Ω (N^1/2) has been conjectured. We disprove this conjecture, presenting a generic algorithm with complexity o N^1/2) in any group. The worst case occurs when G is a cyclic group of (unknown) prime order, but for approximately half the integers N ε [0,M], the complexity is O (N^1/3).

We prove that a generic algorithm can perform any number of order computations in near linear time, plus the cost of a single order computation with N = #955;(G), where λ(G) is the group exponent (without knowledge of λ(G)). We show that in abelian groups, λ(G) can be computed for the same cost, and also consider some non-abelian cases.

We then use λ(G) to compute the structure of an abelian group. Given an O (N^2-ε) bound on |G| = N, we can compute group structure in o (N^1/2) group operations for all but a small set of pathological cases. The complexity is essentially that of an order computation on a single random element. A lower bound of Ω N^1/2) had been assumed, based on a similar bound for the discrete logarithm problem.

We apply these results to compute the ideal class groups of imaginary quadratic number fields, a standard test case for generic algorithms. The record class group computation by a generic algorithm, for discriminant ?4(1030 + 1), involved some 240 million group operations over the course of 15 days on a Sun SparcStation4. We accomplish the same task using 1/1000th the group operations, taking less than 3 seconds on a PC. Comparisons with non-generic algorithms for class group computation are also favorable in many cases. We successfully computed several class groups with discriminants containing more than 100 digits. These are believed to be the largest class groups ever computed.