Example from CM-Z (page 811): (The only other example, the one on page 793, seems too simple, though is a unitary PRDG to begin with) Worked on CM-Z-EX-811. Obtained the same decomposition as given in the paper. If we unitarize, the unitarized graph also seems to have the same decomposition tree (did not work on it completely). The maximization along the diagonals seems to be working, for the decomposition. Obtained the correct separating vector.
What are the definitions and intuitiuons of separating vector, witness vector and g(lambda) from the example?
How is the vector lambda different from the scheduling matrix? Since lambda is a separating (column) vector, it is used to decompose the graph. The kth row of the scheduling matrix (where k is the depth at which lambda is found), may be a simple function of lambda.
Since CM-Z are talking only about a vector lambda, is it that they donot do a multi-dim scheduling? The main problem that CM-Z handle is detection of ZC. In a later section, they mention how their algorithm can be applied to scheduling and say that MDS is a simple extention. The depth of the decomposition tree in the example they give is 2, which means that it (cannot have a linear schedule) and has to have a multi-dim schedule.
--
To do: To Find definitions of ORTH, CIRC, lambda, partition?
To do: The problem that CM-Z solve is problem 4.7. read problem 4.7
To do: Read fast algorithms for All Pair Shortest Path Problem and methods of solving the problem for unitary graphs.
--
To do: Is the unitarization along diagonals right? POSTSCRIPT: WHAT DOES THIS MEAN??
--
What kind of graph, unitary or normal, will we be giving to the APSP solver. If it is unitary, can we do better?
--
From Ziegler's book on Polytopes: convex polytopes and non-convex polytopes are equivalent mathematically, not algorithmically. What does this mean? Also, this will be explained in chapter 1 of the book.
--
a d-dimensional crosspolytope == simplicial polytope
--
There are a few variants of Farkas lemma. They are based on
--
It seems that the theorems on polytopes become really nice, simple for when the underlying polygons are regular n-gons, called simplicial polygons.
--
JargonWatch: Affine multi-dimensional scheduling of unitarized polyhedral reduced dependence graphs using a decomposition of Karp-Miller-Winograd
--
When we unitarize the PRDG, of the (n+d) dimensions, we obtain a n-gon in all dimensions. The surface lies inside a unit sphere of (n+d) dimensions. The question seems to be which diameter of the sphere has the greatest weight (measured as the largest number of edges parallel to it). What if we take an arbitrary diameter and split all the edges into three classes, (i)ones parallel to it, (ii)ones in a "greater than" direction to it and (iii) ones in a "lesser than" direction to it. The greater than direction can be determined by evaluation of the dot product of that particular vector with the pivot. The lesser than, also can be done similarly. Once the partitioning is done, the algorithm can work on any of the three poartitions greedily Is this right???
--
Why is can we not find the median of the slopes of the vectors? This can be found in linear time.
Posts
