Thursday, March 18, 2010

What would I do with 48 cores

If I had access to 48 cores and 128 GB of RAM, I would use the computational power to resolve the more than half-century old Hirsch conjecture, which states that a polytope in 'd' dimensions with 'n' facets has a diameter less than 'n-d'. Example: for a cube in 3d, the cube has 6 facets. The diameter of the cube (the maximum distance between any 2 vertices) is 3. Thus atleast for the 3-cube Hirsch is true. Hirsch has also been shown to be true for d=4,5 and recently d=6. Using a cutting plane algorithm I have designed a combinatoric enumeration system which can generate all possible counter-examples to Hirsch, but since the number of polytopes is exponential and the enumeration requires significant computational power, no one has ever searched for counter-examples in high dimension, such as d=12. On d=7, the computer generation on a dual-Opteron 242 machine has been running for 8 months.
http://skoranne.blogspot.com/2010/03/more-polytope-experiments.html
http://skoranne.blogspot.com/2009/10/polytope-enumeration-system-hits-new.html
A 48 core machine with high speed memory connection would be sufficient in either (i) showing a counter example of Hirsch, or (ii) extending the known dimension where Hirsch is true upto 12.

In addition to being the single most fundamental problem in Operations Research, Hirsch, also has practical applications to Linear Programming. Any advances made in this domain would translate to immediate benefits in the simplex algorithm.

It is my opinion that rather than solve a single problem, such as climate modeling, or folding, or even natural resource and food resource scheduling for under-developed nations, we, as computer scientist should target the fundamental algorithms for optimization, which when improved, can benefit in providing better solutions to the complex problems we all face in the 21st century.

1 comment:

  1. Hi! I have a book called "Computing on Cell Broadband Engine" written by you... I have to make some of those examples, but I have problems in finding the header file "util.h" and the library "mc_rand.h". Can you send me some informations, please? Thank you! gygy_x@yahoo.com, istefan@stud.eed.usv.ro

    ReplyDelete