Monday, July 11, 2005

Separating hyperplanes, witnesses for unitary graphs

A separating vector is a vector which belongs to the dependence cone.
A witness is a special form of separating vectors: One that induces only +ve cycles in the given graph.
To Do: Read DRV or DV-KMW and draw the dual polyhedron for the examples from KMW.
To do: DRV has a PRDG in chapter 5. work on it.
The hyperplane/cycle algorithm doesnot seem to work when all the weights are (0,0,0). Is this a case that can be handled easily?
Example from DRV-EX-213: The input graph is already in unitarized form. DRV say that all the vectors that are orthogonal to (1,0,0) vanish. Our algorithm identifies the plane i=0 (the one orthogonal to (1,0,0)) to be, what CM-Z would call, a separating hyperplane . The edges from S2 to the bottom node and a two more edges disappear.
A few questions: What about the edge from S1 to the bottom node? Why does it not disappear? What about the vectors (0,0,0)?
Prove/disprove the following (important) : The unariness of the vectors (q,v).
Soln(of vector (q,v)): The vector q need not be unitary. A graph with three edges having the vectors e1=(1,0), e2=(-1,+), e3=(-1,-1) would have the solution 2q1 = q2 + q3. A circulation would be (q1,q2,q3) = (2,-1,-1), which is not unitary.
Possible choices for the Level sets: (1) The norm, (2) square of the norm (3) number of non-zero components in the dependence vectors
One more advantage of unitarization: The level sets of the vectors are from a finite set. If the dependences are not unitarized, the level sets are from a possibly infinite set.
Here may be the tentative algorithm:
(1) Unitarize the graph
(2) Find the set of edges with the largest level sets. This can be done by
(a) finding the largest level set
(b) selecting the edges with norm == that particular level set
(3) Amon the edges with the greatest level set, find the plane which is parallel to the maximal number of edges. This can be done by ........
The Unitarization Problem: Unitarization for ZC-D, multi-dim scheduling, MDS followed by optimal memory allocation, simultaneous MDS and OMA, tiling for parallelism, tiling for locality.
To do: How does the dual polyhedron look like? What is special about it when it has been unitarized? How do its level sets look like?