depth of the decomposition tree

Analogies for decomposition tree: If you compare the decomposition tree of KMW with the comparision tree of a sorting algorithm (like QSORT), strange things come into picture. The analogy between these two -- lets call them KMW-T and QSORT-T -- makes sense. We are decomposing the input, which is a graph in KMW or an array in QSORT, by a criterion and constructing a tree which stores at the internal nodes, the certificates for the decomposition and at the leaves, the individual components. However, the KMW-T need not be a binary tree, while the SORT-T has to be binary, because of the linear order in the latter.
So, a better comparision of KMT-T is with the decomposition tree of an algorithm that detects Strongly Connected Components in a directed graph. Call such a tree, as SCC-T. Both the KMW-T and SCC-T look for some kind of "weakly connected components" and break the edges that connect them. At the leaves of both the trees are components which cannot be decomposed further (they could be trivially, individual nodes). At the internal nodes of both the trees are some kind of "certificates", which can be used verify the validity of the decomposition. Both the algorithms are greedy(?) and recursive in the sense that they do the same on the smaller components. Both the algorithms are top-down.
Postscript (added on 9-JUL)If we want to be more precise about the certificates etc, look up the example in Schrijver book, about Planarity testing of Hopcroft-Tarjan. They reduce the problem into bipartite testing and planarity testing of smaller graphs.
--
Question: Is there any bottom up SCC algorithm? If there is one, can KMW-T be constructed in a bottom-up fashion? Given the KMW-T, QR are doing a memory-allocation, traversing it bottom-up(Is this right?). If so, can it be done top-down, using the certificates and at the same time as a certificate is obtained?
--
fact: A decomposition tree never has a depth of more than n. This seems easy to prove: At a level if the decomposition algorithm is run, atleast one node of the PRDG gets disconnected, or we have a ZC. Is this a situation that we want to avoid, or having a \Theta(n) depth is good?
--
What is the difference between the parallelism obtained between two PRDGs, each with n nodes, that induce a O(log n) depth decomposition tree and O(n) decomposition tree? More importantly, what propery of the graph makes it induce a KMW-T of depth of O(log n) or O(n) or O(1)? This is a more important question because, the depth of the tree is a property of the graph, not of the algorithm. What property? How can it be detected, in other ways? How can you design an algorithm which gives another depth for the same graph? Why are constant depth trees more useful/interesting?
Question: Is the separation of the components of the graph based on a weakly separating hyperplanes the right way for obtaining maximal-parallelism or even, minimal-memory-allocation? Can we think of a median-separating hyperplane (ala median) that divides the components (collection of nodes and edges) equally?
Is this the only way of decomposing the tree?
--
Most of the above questions can be answered by knowing more about KMW-decomposition and reasoning about the hyperplanes which separate some components. How, why and is that the only way?
--
CM-Z ideas: independent subspace, maximal independent subspace is the same as separation of the space into independent isomorphic flats
--
To do: Get the definitions of weakly and strongly separating hyperplanes from DV-KMW. There are many types of separation of convex polyhedra by a hyperplane like "freely separated", "properly separated", "strictly separated" and "strongly separated" Some of them are explained intuitively here (a pdf link). The lecture notes is from a course on non-linear optimization. The course page is this. Look at the lecture notes and recitations.
To do: Understand the notions of separating hyperplanes from KMW with an example and frame an example when the depth of the decomposition tree is n and hence write the parallel code.
Question: What notion of separating hyperplane do CM-Z use?
--
Separability is important for ZC-detection and multi-dimensional scheduling. How is it useful for memory-allocation? QR do a (1) ZC detection followed by (2)MDS followed by (3)optimal-memory-allocation. Can all of (1), (2) and (3) be done together with a convex kind of solution?
--
Worked the examples from KMW (two nodes and depth 2 on page 577, two nodes with depth 1 on page 585 and two nodes with depth 2 on page 585), DV-94-24 (lone example, depth 2), DV-KMW??????? some edges simply disappear, !!!
Arbitrarily unitarized the KMW-EX on page 585 (fig7). The depth of KMW-T is still the same (see theorem below).
Note: the example (fig 7) of KMW on page 585 with depth 1.
To do: KMW big example?
--
Theorem: The depth of the decomposition algorithm is invariant to unitarization. Proof????
--
notes about TUMity: a self edge only induces zeroes on its incidence matrix. multiple parallel edges donot spoil the TUMity of the incidence matrix as they are different edges.
--
What has the TUMity of the unitarized graph has to do with a decomposition tree of height 1?????
--
The page has corrections to the Tarjan's book. They are the ones that I have noticed before.
--
The QR algorithm needs the (possibly multi-dimensional) schedule for each variable. Can the memory optimization be done in tandem with the KMW-decomposition algorithm?