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.

Thursday, March 11, 2010

Python Polytope Perfect


I am a Common Lisp fan, so never bothered to look at Python in great detail until the need for polytope visulization and Anand's gentle prodding to try NetworkX and Ubigraph tempted me.

Python is so close to Lisp; it was almost like coming home. I picked up the syntax as I went along, and within 2 nights I had put together an interactive shell around the polytope explorer.

Example:

def CalculateHeritage( P, i ):
"""Given the polytope table and the polytope index find its heritage"""
answer = []
parentId = P[i].parentId
while i != parentId:
answer.append( (parentId, P[i].cut_set ) )
i = parentId
parentId = P[i].parentId
return answer

Anyone who has written lambda defuns, or docstrings can see the "inspiration", anyway who cares its good that they have implemented a good subset of Lisp.

Object-oriented programming is also there, ala, CLOS thrown on the existing language.

class Polytope:
"""Facets, Fvector, signature and parent information"""
def __init__(self):
self.facets = []
self.fvec = []
self.signature = ""
self.parent = 0
self.parendId = -1
self.cut_set = []
def dump(self):
print self.signature
print " "
print self.parent
print " "
print self.parentId

But the main advantage of using Python comes here:
def ParseFile( fileName ):
print "Reading file %s" %fileName
if polytope_file_name.find( '.gz' ) != -1:
file = gzip.open( fileName, 'rb' )
lines = file.readlines()
file.close()
else:
f = open( fileName, 'r' )
lines = f.readlines()
f.close()

Just using "import gzip" gave me the ability to compress my data set from 1 Gb to 65 Mb, and still retain the ability to use the data.

Using matplot and NetworkX I got the 4-pane visualizer; left top shows original
polytope, below it the induced cut-set, right top is the graph remainder and right
bottom is the produced polytope graph. You can iterate over the polytopes by specifying which vertices to truncate.

Anand thinks linear cuts will not increase the diameter and the interactive system has confirmed it so far, but the proof is worked on.

Summary: Python is like Lisp, I like Lisp => I like Python.

Sunday, March 7, 2010

More polytope experiments

Anand has been visiting for the weekend and we have been working on enhancing the visualizer he has written to see the high dimensional polytopes. The enumeration software has also been enhanced and is much faster now.

Here is an example:This is the 4-prism generated from the 4-simplex by deleting any vertex. Now if we move a hyperplane to truncate vertices 3 and 7 we get

The final cut is 4 vertices, { 4, 8, 11, 14 }. Truncating these gets us the beautiful 4-cube which I had alluded to in an earlier post.

The actual face-lattice for the 4-cube produced by this cut is
VERTICES_IN_FACETS
{ 0 1 2 3 4 5 6 7}
{ 0 2 4 6 8 10 12 14}
{ 1 3 5 7 9 11 13 15}
{ 0 1 2 3 8 9 10 11}
{ 0 1 4 5 8 9 12 13}
{ 2 3 6 7 10 11 14 15}
{ 4 5 6 7 12 13 14 15}
{ 8 9 10 11 12 13 14 15}

If that is not poetry, I dont know what is. As Hardy had said "It must be true, as no one will have the imagination to invent something as beautiful....".

Cut sequence for the interactive enumerator are;
1
0
1
2
1 5
1
4
4 8 11 14
0