Notes on KMW and DV: chapter4

Notation

Notation for graphs: KMW call as dependence graph, what we now know as RDG. KMW donot give a name to EDG. KMW call a path as pi. It could be used to define a cycle and simple cycle. Also, its length could be inf if its length is infinite. The cycle and simple cycle are defined only for paths whose length is not inf. (We have to be a little careful about undefined and inf here.)

Other Notations: From KMW KMW use the functions: T, S, F, F_n (they are different), phi_s. S is any schedule. T is the free schedule, the fastest possible schedule. F is defined to test for presence of free schedule. F_n is the positive orthant in the n dimensional Euclidean space. From the book, the notations are: T for any schedule, T_f is the free schedule and F is defined for presence of free schedule, F_n is the positive orthant. phi_s (see later for a proper definition and a possible intuition).

More notices from the notation department: Gamma and EDG in DV and KMW are (slightly) different: The Gamma that KMW define is an EDG with dependence edges. The EDG that Darte-Vivien define has edges that mean data flows. The difference in definitions means changes in simple things like whether the longest path has source or sink of a vertex (k,p) in the EDG. Sticking to the notations in the book seems to be useful.

RDG having depenendence edges/data-flow edges
The equations being defined by a_j = ... a_k(z - w) ... or a_j = ... a_k(z+w)

Relation between Brent's theorem (1974) and KMW's statement of computability:

Computability

Conditions for computability: KMW give both the necessary and sufficient conditions for computability of a RDG. The intuitive definition: An SURE is computable if there exists a schedule for it. In other words, an SURE is computable if every vertex in its EDG is computable.

Computability of a SURE over a bounded domain: Since we usually deal with bounded domains, the computability problem boils down to testing for acyclicity of the EDG. This works, but it is very costly and input size dependent (ala Ford-Fulkerson algorithm for maxflow). Further, this method cannot be applied to unbounded domains.

A note fom Quinton-Saouter-1203 (QS): When the domain is allowed to be unbounded, the SURE is (trivially) incomputable. This result was proved by Joinnault. Most realistic algorithms have bounded domains. QS say that the result may not be that useful and that the interesting cases are the computability questions of SUREs defined over domains of bounded size. Also, QS give the condition for incomputability of Parametrized Uniform Recurrence Equations PUREs and PAREs. (See the nice figures at the end of QS-paper for figures of PUREs which are computable and which are not. The difference being a change in the value of a parameter.)

EDG: Assume we use the Darte-Vivien's notation of edges in the EDG meaning data flow. An EDG is computable iff for all points (i,p) in the EDG, all paths ending at (i,p) are of finite length.

Size of Domain: unbounded and entire positive orthant: Darte-Vivien (chapter 4, theorem 17) give the condition for computability of a SURE defined over entire positive orthant (which is an unbounded domain). It seems that the notion of unboundedness is limited to equations defined over positive orthant (not the entire space: I donot know why and its implications). If a SURE is defined over unbounded domain (meaning positive orthant), then it is computable iff G there is no nonpositive weight cycle in it (where G is its RDG).

Size of domain is bounded: Darte-Vivien (chapter4, theorem 18) give the relationship between the computability and the zero-weight cycles in any SURE defined over bounded domains. Basically, they show that a SURE defined over a bounded domain is computable iff G has no cycle of zero-weight. The phrase "All systems of uniform recurrence equations defined from a RDG G" makes more sense once we understand the definition of a RDG is (quite) independent of the domain of the underlying SURE (the usual definition of a RDG does not encode the domains of the variables). So a RDG can induce many SUREs, each in a bounded domain.

Fat domains: The computability of a SURE defined over bounded domain makes sense iff the domain is sufficiently fat. Read more about this.

Schedule

Schedule: A valid schedule respects the dependences of the SURE. If an SURE does not have such a schedule, then it is said to be incomputable. Examples are either a node in the EDG depending on itself, or a node in the EDG at the end of infinite path before its operands are ready.

Free schedule vs. Linear schedule: KMW donot use the concept of linear schedule (it seems that they donot even use the term: I did a text search). They use a concept of free schedule. Darte-Vivien show that free schedule could beat the fastest linear schedule by a constant, independent of the size of the domain.

Questions: What do KMW mean by bounded and unbounded parallelism? What about the notions of tube (which intuitively means bounded along a dimension)? What about the storage requirements?

Questions on definitions of Schedule S(k,p): As defined on page 566, A schedule seems to be similar to that of a 1-d schedule as we know now. This is because, they talk about every vertex of the EDG getting a 'single time stamp'. But, that does not preclude many vertices getting the same time stamp (right?).

Free Schedule T(k,p) If a vertex of EDG does is free, we evaluate it at time 1. If all the operands of a vertex of the EDG are available at time t, we evaluate the point at time t+1.

Machinery on page 566 involving T and F: From the outside, T and F seem so similar. T gives us a recursive definition and F looks like the expansion of the recursive definition given by T. However, there is a critical there exists clause in the definition of F. That is very crucial to understand that length of a path could go on to undefined values as given by the definition of T. Is there something we need to act here??????

=============================

Section 3: Lemma 1 notes

[Also refer to notes from Berge. This is the link.]

Lemma 1: premise: Number of edges directed out of each vertex is finite. C1: If there is no upper bound on the lengths of paths directed out of vertex v, C2: there exists an infinite path directed out of v.

Strategy to prove that the premise is required: P => (A=>B) is the given structure of lemma. Why is the premise required? The necessity of the premise can be proved by assuming that it is false, i.e., NOT(P) is true. In that case, if we find that the clause (A=>B) is false, we are done. in other words, we should prove that NOT(P) is true and NOT(A=>B) is true. or, that NOT(P) is true and NOT(NOT(A) OR B) is true. or, that NOT(P) is true and A AND NOT(B) is true.

An infinite graph has a vertex w such that outdegree(w) is unbounded. There are two interesting cases: either there exists a path from w to v or there exists a path from v to w. Let us prove for the case when there is a path from v to w(the other case: when there exists a path from w to v can be proved with a similar argument. The third case: when there does not exist a path between v and w blows away the negation of the premise).

There exists a path from v to w. Also, There is no upper bound on the lengths of paths directed out of vertex v. Also, there does not exist an infinite path directed out of v.

Should we give a example or prove the fact? If we give an example, which would be a counter example to the fact that the premise is not required, we are done.

Proof of the Lemma and related notes:

====================

Lemma 1: Let H be a directed graph in the edges directed out each vertex is finite. Then, if there is a no upper bound on the lengths of paths directed out of vertex v, there exists an infinite path directed of v.

Proof strategy: A => B => C. Assume A. Assume NOT(C). If it leads to NOT(B), then we have a contradiction. which proves that B => C.

Proof: Assume the premise. Assume that there does not exist an infinite path directed out of vertex v. Then the longest path directed out of v is the function 1 + max{}. This function is a recursive function defined with peano arithmetic. So, there exists an upper bound on the lengths of paths directed out of vertex v. This is a contradiction with the hypothesis.

Proof 2: The graph is progressively finite. Prove that it is progressively bounded. [The key idea is to get that a finite set has an upper bound.] The set of its descendants is finite.

Proof for the premise: prove that if the graph is progressively finite and not progressevely bounded, there exists a vertex whose outdegree is not finite. This will be contradiction.

The statement actually says that if A (as usual, Gamma-finite), then if it is not progressively bounded, it is not progressively finite. This is the same as saying that if it is progressively finite, it is progressively bounded. (same as if it is (not progressively finite) or (progressively bounded)).

To prove the premise, we have to say that, if it is progressively finite and (not progressively bounded), there exists a vertex whose outdegree is infinite.

Given that there exists no infinite paths and that there is no upper bound on any paths, k*Gamma(x)

=========================

Why do we need the premise? Contrary to the premise, assume that there exists a vertex w which has infinite number of edges out of it. Case 1: If there exists a path from vertex v to vertex w -- regardless of the number of edges out of vertex v -- there exist infinite number of paths out of vertex v. This is because, a path from vertex v to vertex w is all we need (this is why we started from the assumption that the graph is connected). The set of infinite edges out of vertex w lead to infinite number of paths out of vertex w: they are the following: {[v->w,w1],[v->w,w2],[v->w,w3],...,[v->w,wk],...inf}. Case 2: If there exists no path from vertex v to vertex w (or any vertex u which has infinite number of edges out of it), then the premise is not needed for the lemma. Is this right?

Counter example: So a counter example would be an infinite graph (finite graphs are not that interesting) with the folllowing properties.

To remove some of these owes, we can assume that the graph is a connected graph.

In all the proofs here, we assume the premise and prove the lemma.

Proof by deduction:Assume the premise. also assume C1, that there is no upper bound on the lengths of paths directed out of vertex v. for a vertex v, let us define a set S_v, which is the set of all paths from the vertex v. Define L(S_v) as a function, which returns a set L_v, each of whose elements are integers denoting the lengths of paths of elements of S_v.
Since there is no upper bound, the function must return inf. Which is another way of stating C2. Is this right?

Proof by deduction: Assume the premise. also assume C1, that there is no upper bound on the lengths of paths directed out of vertex v. There exists two cases, when the graph is finite (|X| is finite) or not (|X|=inf). case1: the graph is finite: As there is no upper bound on the length of paths out of vertex v, v participates in a circuit. This means that we can obtain paths of *any* length and without bound from v. This means that we can obtain a path of infinite length from v. Q.E.D (???check this proof for circularity???)

Proof by contradiction: Assume premise, assume C1 and negation(C2): case 1: the graph is finite (|X| < inf): NOT(C2) => there is no inf path directed out of v => all paths out of v are of finite (but possibly unbounded) length => there exists a vertex w which is at a maximum distance from v. Let us call this distance k. => all paths out of v are of length <= k. This means that there is a upper bound on the lengths of paths. A contradiction. case 2 (|X|=inf): If the graph is connected (there exists a path between every two vertices), every vertex participates in a path of unbounded length. Which means that the statement is obviously true. If the graph consists of more than one connected component, we can apply the argument of case 1 to the component which contains v.

Assume premise, assume C1, assume NOT(C2): NOT(C2) means that there exists no path of infinite length out of vertex v. Since vertex v has finite outdegree (premise), there does not exist a path of infinite length out of each vertices belonging to the set Gamma(x). This means that ......... ..........

We have to use the fact that v does not praticipate in a path of infinite length. Let us assume for now that an infinite path length is obtained by a circuit. from premise, let us assume that w1,...,wn are the vertices adjacent to v. None of w1,...,wn have a path back to v. This means that the set Gamma(W) is strictly greater than Gamma(v). This means that Gamma^hat(v) is an unbounded set. What do we do with these sets...

proof by contradiction: Assume premise. Assume negation(C1) and C2: NOT(C1) => there exists an upper bound on the lengths of paths directed out of vertex v. => All paths through v are of length <= l. This means that there is no path of length inf thro v. A contrtadiction with C2.

Proof by induction


proving an iff by contradiction of the if and only if part is kind of funny ...

=================================

Explicitly Defined vs. Computability: KMW use explicitly defined for a variable a_j(p) instead of talking about its computability. An SURE is said to have a schedule if each of its variables is explicitly defined (page 566 in the paper and cor.3 in the book). This also means that, an SURE is computable if each of its variables is explicitly defined. (we are using the relationship between computability and the existence of a schedule.)

Bounded Parallelism (page 566): phi_s(s,tau): Given a schedule function for every vertex of the EDG (k,p) (if S(k,p)=tau) phi_s(s,tau) is the cardinality of the inverse of the schedule function S.

Intuitive explanation of phi_s: Given a k and p, it is the number of

Intuition behind phi_s: A given schedule maps the vertices of the EDG into N (as it associates a timestamp with every vertex in the EDG). Given a variable of the SURE, phi_s is the cardinality of the number of vertices of the EDG of that type that have the same mapping???? Also read section 4 for another explanation of phi

It is not clear why phi_s should be parametrized on k also. If what we are interested is bounded parallelism, why not just talk about the cardinality of phi_s(tau) = || p | S(k,p) = tau || k = 1...m and tau = 1,2,...

May be they mean that. This opinion is because, the next line, they say 'for all k and tau'. So the notion of bounded parallelism has nothing to do with the 'type of vertices'. OTOH, the definition of phi_s can be general enough that it can encapsulate other ideas??

=============================================

Section 3:Conditions for a function to be explicitly defined

[With Lemma 1, the stage is set about infinite graphs and relationship between existance of upper bound on the length of the path and presence of a infinite length path. The theorem 1 gives a definition of computability.]

Notation: non+ve: A vector q is nonpositive if q_i <= 0.

Difference between nonpositive (defined on page 567) and semi-positive (defined on page 569): A vector in 2-dimensions, is nonpositive if it belongs to the (i) third quadrant, or (ii) -ve y-axis or (iii) -ve x-axis or (iii) is the zero-vector. A vector in 2-dimensions is said to be semi-positive if is belongs to the (i) first quadrant or (ii) +ve x axis or (iii) +ve y-axis.

Note: The regions are mutually exclusive. There exists vectors which are neither. The following "picture" encapsulates all the above ideas.


                                ^
                                |
                                ssssssssssss
                                ssssssssssss
                                ssssssssssss
                                ssssssssssss
                                ssssssssssss
                                ssssssssssss
<-nnnnnnnnnnnnsssssssssss->
    nnnnnnnnnnnn
    nnnnnnnnnnnn
    nnnnnnnnnnnn
    nnnnnnnnnnnn
    nnnnnnnnnnnn
    nnnnnnnnnnnn
                                |
                                v


[The computability of a SURE and its relation to the presence of positive weight cycles.]

KMW-Theorem 1 statement: Let G be a dependence graph [meaning RDG] specifying a SURE defined over F_n [the positive orthant]. Then the function a_k(p) is explicitly defined iff G does not have a path from v_k to any vertex v_l contained in a nonpositive cycle.

Ambiguity in the statement of theorem1 (in KMW): The statement of the theorem is a little ambiguous and cannot be disambiguated easily in particular, by reading the statement without context. The first meaning is obtained by associating the clause "contained in a nonpositive cycle" with path in the following way: "... G does not have a path, from v_k to any vertex v_l contained in a nonpositive cycle". The other interpretation is to associate the clause "contained in a nonpositive cycle" with the vertex v_l in the following way: "... iff G does not have a path from v_k to any vertex v_l contained in a nonpositive cycle".

Disambiguation of the statement of theorem 1 (in KMW): Method 1: just reading the statement: If we associate the clause with "path", then v_l seems to be redundant in the theorem. On the other hand, if we associate the clause with vertex v_l, then everything falls into place, there is no redundancy in the definition, and there is a more precise definition of the path. Method 2:reading the first line of the proof: The first line of the proof says "Suppose there is a path pi from v_k to v_l and a nonpositive cycle C including v_l as shown in ....". This means that (i) v_l is in a nonpositive cycle (ii) there is a path from v_k to such v_l.

A possible better wording for theorem1: If you donot like the statement of theorem because of the above ambiguity and also the idea of a cycle being 'out of a vertex' is kind of ugly, use the word: reachable. However, it is more precise talking about the explicit-definition of a vertex, rather than the computability of a system. The reason is that some of the vertices of the RDG may not be explicitly defined, but others may be explicitly defined. rewording: A variable a_k of the SURE is said to be explicitly defined if in the RDG of the SURE, no cycle of non-positive weight is reachable from the vertex corresponding to a_k.

[A better statement would be the following: Any vertex which 'participates' in a non-positive-weight cycle is not explicitly defined. Any vertex that has a path to another vetex that 'participates' in such a cycle is not explicitly defined. The maiincrib about this statement is the use of the word 'participate'.]

[Darte-Vivien divide the theorem into two parts, corollary 3 and theorem 17.]

The different kinds of statements of computability from DV/KMW -- The equivalence of three (many?) things: There equivalence of the following things is being talked about: (i) cycle of nonpositive weights in RDG G (ii) incomputability of the SURE S (iii) path of infinite length directed out of vertex (i,p) in EDG Gamma (iv) not every variable of the SURE to be explicitly defined (v) absence of a schedule.

Darte-Vivien's equivalences: In DV, the equivalence of (ii) and (iii) is by definition (and the existence) of free schedule and also by corollary 3. What about the equivalence of rest of the things in DV?

KMW's equivalences: In KMW, the equivalence of (iv) and (ii) is by definition of computability (remember, KMW donot use the word computability). Also, the equivalence of (v) and (ii) is also by definition of computability and schedule. KMW bring lemmma 1 into context because, it gives the equivalence of "absence of explicit " and "presence of infinite length paths": namely the equivalence of (iv) (or even (v)) and (iii).

[All this is required? Yes. The equations are a simple description of the input. We have some associated questions on the input which we want to answer in finite time. The computability problem of the SUREs maps directly to checking for intinite length paths in the EDG. Direct checking is not a feasible way. We map the problem to checking for positive weight cycles in the RDG.]

DV: Corollary 3: The equivalence between (ii) and (iii) is made. The statement: "A SURE is computable iff whatever the vertex (i,p) in Gamma, there is no infinite path in Gamma directed to (i,p). "

Darte-Vivien's statement of the theorem 17: Let G be the RDG of a SURE S defined over F_n (the +ve orthant as domain for all variables). S is computable iff G has no cycle of non+ve weight i.e., w(C) <= 0.

KMW's proof strategy: The theorem statement talks about equivalence of (i) and (iv). KMW have however stated on page 566, the equivalence between the existence of a schedule and each variable of the SURE being explicitly defined (meaning they have the equivalence of ??? ). So they prove theorem 1 by proving the equivalence of (i) and (iii).

Darte-Vivien's proof strategy: The theorem statement talks about equivalence of (i) and (ii). Darte-Vivien have however proved in corollary 3, the equivalence of (ii) and (iii). So they prove theorem 3 by proving the equivalence of (i) and (iii).

KMW statement of corollary 1/2: From the outside, it may look that KMW's cor.1/2 and the statement of Theorem 18 from DVR are different. Howwver, They are the same and KMW donot miss any trick.

Corollary 1: In corollary 1, KMW say that

[just to remember: we are proving the equivalence of (i) = "absence of a cycle of nonpositive weight in G" and (iii) = "absence of a path of infinite length directed out of vertex (i,p) in Gamma". Actually, we are proving the contrapositive: (i)="presence of a cycle of nonpositive weight in G" and (iii)="presence of a path of infinite length directed out of vertex (i,p) in Gamma".]

The proof: (i) => (iii): method induction: If there exists a cycle of nonpositive weight in G, then exists a path of infinite length directed out of some vertex (i,p) in Gamma. Assumption: p, p-w_j for all 1 <= j <= k are in G_n (all these are valid labels for lattice points in the positive orthant). Given: there exists a cycle of nonpositive weight in G => Let i and j be two (not necessarily different) vertices in G. Let the weight of the cycle be w1 as i to j and w2 from j to i. w1 + w2 is a nonpositive vector. Now, ......??? ?????

[Punch line of the proof: w(C)<=0 which means that there exists a ll such that (ll,p-w(C)) is reachable from (i,p). So we can repeat the above procedure ad-infinitum, or give an inductive proof.]

[The statement of the only-if part talks about (iv)=>(i). KMW use the definition of explicit-definition of a variable to say that (iv) is equivalent to (iii). Also, they use lemma 1 to show that (iii) is equivalent to the existance of a specific infinite path.]

The proof: (iii) => (i): There exist an infinite path. We can select a infinite subsequence of the infinite path (i,p) such that the 'p' is non-decreasing, first in the first coordinate, next in the second coordinate etc. This is a list of infinite length [this is because, if it were not, the list is of finite size: ]. It is a cycle, as the coordinates 'i' have to repeat, by pegion-hole principle. This is a cycle of +ve weight, as the p is non+ve.

Possible bug in Darte-Vivien's statement/proof of theorem 17: Darte-Vivien use n differently in the proof of theorem 3: In the theorem statement, n is used as a superscript of mathcal{N} signifying the dimension of the input. In the inductive proof for the "if part", DV use n again -- this time as a variable for induction -- which could result in confusion. A better way is to use alpha, as KMW use.

===========================

My statement of the above theorems: Let S be a SURE. with G as its RDG and its Gamma as its EDG (with dependence edges). The following are equivalent: (A) S is computable. (B) G does not have a vertex v which belongs to a path of infinite length (or every vertex of G is explicitly defined) (C) No vertex in the EDG Gamma has a path of infinite path out of it (into it?).

============================

Proof of Darte-Vivien's theorem17: if part (suppose there is a cycle of non+ve weight. then the SURE has an infinite path ending in ......)

Comment about DV's theorem's 17-18 (or even KMW's theorem 1 and corollary's): Though the statement for the incomputability of a SURE defined over F_n is relatively more interesting, the pragmatic view seems to be to talk about the computability of a SURE defined over a bounded domain (so that we restrict our discussion on just for loops here: see the remark about while loops later). In order to remove the cases when the RDG is computable for some domain sizes and not for others, its better to talk about the incomputability of SURE over any bounded domain. DV and KMW differ here a little. DV talk about the computability of a SURE defined over the families of any finite size domains.OTOH KMW talk about the computability of SUREs defined over strips of F_n (intuitive meaning defined below).

[corollary 1 of KMW talks about the extension of theorem1 to strips of F_n]

Meaning of strips: KMW use the notation Q_t * F_{n-t} to mean the following. (The implicit assumption is that t <= n.) In each of the t dimensions, the set of coordinates in those t dimensions is from a finite set. In the other n-t dimensions, the sizes of the coordinates is not of a finite set.

[idea of KMW's proof of corollary1: Draw a RDG G' in which the vertices are from {1, ... , n} * Q_t. This is a finite graph and can work as the RDG. Now apply theorem1 to the EDG induced by this RDG.]

Corollary 2:

Question about the strips and the scheduling of while loops (n-t while loops out of n dimensional space): Given a n dimensional SURE with only t dimensions are from a fiite set, can the loops be scheduled so that the performance of the overall code be improved? What is the best schedule for the code? What is the best memory allocation for the code?

[KMW talk about strips of F_n in corollary 1 and 2. Darte-Vivien's statement of theorem and its proof are the same as that when t = n; or, when the SURE is defined in a finite domain.]

KMW's corollary 1 of theorem1: Let G be the dependence graph of a SURE defined over R=Q_t * F_{n-t}. Then a_k(p) is explicitly defined iff there donot exist l in {1, ... , m} and p,q,r in R such that (i) (k,p) -> (l,q) -> (l,r) (ii) the vector q - r is zero in the coordinates corresponding to Q_t and nonpositive in the coordinates corresponding to F_{n-t}.

Ambiguity in the statement of KMW-corollary 1: As stated in KMW, corollary (i) talks about the SURE, the EDG and the RDG at the same time. OTOH, corollary 2 talks about only the SURE and the RDG, just as in the spirit of theorem 1. Darte-Vivien remove the need for this type of reasoning by giving "their corollary 3" apriori.

[See the reasoning above which states that the statement of theorem1 is ambiguous. In the samw way, corollary 2 also is ambiguous.]

Questions about strips: Give a statement of computability of an EDG defined over a skewed strip like {i-j <= 10; i-j >= 5; i >= 0; j <= 0}

Variant of theorem about UREs for bounded domains

=======================================

Section 4: The theorems for URE

Notation: Semi positive: a vector q is semi positive if q != 0 and q_i >=0.

Theorem 2: It gives the conditions for the computability of a URE. Basically, it frames the computability problem of a URE as a LP problem and some statements of the theorem are equivalent by Farkas lemma.

In more detail, (i) and (ii) are equivalent by theorem1. Rest by Farkas lemma and duality of the LP.

Examples of separating hyperplanes on page 570:

page 571: for a URE, we can index the function T by just T: m(p) and T(p): remember that

Theorem 4:

Amount of Parallelism (the same as phi_s(tau)): There exists a schedule S such that sup_tau phi_s(tau) = inf.

Intuitive meaning of amount of parallelism:

Notation: sup and inf: According to this link, supremum (aka sup) means least upper bound. infimum (aka inf) means the greatest lower bound. (sup and inf are defined for sets.) The supremum and infimum of a set need not belong to the set.

Storage Requirements for a URE:

sigma_s (secondary objective function??) For an URE, it is the number of computed values that have to be retained at a computation time tau so that other points are computed.

Theorem 5: Memory optimization for a URE: If there exist two (dependence) vectors w_i and w_j which are linearly independent, then there can be no optimization of memory. This is a strong statement because, it applies for any schedule.

What if the dependences are the set (0,1) and (1,0)?

Intuitive meaning of the amount of storage requirements (taken from page 575): Except for special cases, the amount of storage required to compute the function a(p) is unbounded.

=========================

Algorithm not given? (page 580): foot note about constuction of G' It seems that KMW do not give an explcit algorithm for the constuction of G'. They also donot give the running time of the algorithm. I doubt that the method of measuring algorithm by their running time (by Karp/Edmonds/Hartmanis) completed by then?

Page 582: Parallelism: What do KMW mean when they say that they have not solved the problem completely.

Section 5: SUREs

Amount of Parallelism of SUREs when compared with UREs (p577): As shown in theorem The main idea is that there exist explicitly defined systems with n>1 for which free schedule has bounded parallelism. It is not vert clear why only one point of the iteration space can be computed at any time.

Questions about example 6, page 578: Why is are self-dependence loops labelled in a strange way? Also why do KMW seem to imply that this fig.5 can have only sequential schedules? Also, look at their notes for the example when they talk about the free schedule.

Theorem 7: Properties of the subgraph similar to the theorems in DV.

Theorem 8 (page 583):

Storage of SUREs: p 584:

Section 6 (p 588): Implicit schedules

Implicit schedules Vs. Explicit Schedules (page 588):

A Simple preprocessing step (using Euler's theorem) : The KMW decomposition algorithm is searching for union of cycles. We have Euler's theorem that a connected directed graph has a Eulerian Cycle iff each vertex has equal in and out degrees. We can apply this theorem and remove any node v whose indegree is not equal to its outdegree. IS THIS RIGHT? What do do with the hypergraph? What to do with the bipartite graph? What to do with non-simple cycles(remember, Euler;s theorem applies to simple cycles)?

Should we try for free schedule of the hypergraph? Read the rest of this entry >>

hypergraphs, strongly connected components

In a hypergraph constructed in a way mentioned before, we seem to be finding hyper-articulation points (or hyper-articulation edges). The decomposition algorithm seems to remove some hyperedges. The resultant components are somehow, hyper-strongly connected.
--
Assume we do a DFS on the associated directed bipartite graph, also giving each vertex its [BEGIN,END] times as usual. BEGIN meaning the first time when it is found, and END meaning the time when it is blackened, from grey.

Let V -> u -> W be a hyperedge, with u being the "dummy" node corresponding to the hyperedge. Also, let v \in V and w \in W be two representatiove elements of the sets V and W.

fact: END(u) > END(w) for all w \in W /*this is anyway true */
--

((END(v) > END(u)) and () for all v \in V, then node u is not part of any zero-weight cycle. /*the usual cycle condition*/

This can be stated as the following: no B-arc of the hypergraph is a backward edge in a DFS

Now, if the node u corresponding to a hyperedge E has the following property: for every vertex v such that v->u is a B-hyperedge(beginning part of a hyperedge), END(u) >
--
Preprocessing step: How do we we obtain zero-contributions from some edges? i.e., when we have a equation like q1 + q2 + q3 = 0, we immediately write it as q1 = q2 = q3 = 0. What does this mean? So a preprocessing step could remove vertices which have all incoming or all outgoing edges (actually hyperedge components) to it. Then we remove those edges completely (remember, we have to remove the hyperedge completely) from the graph. This is called a preprocessing step, as this can be done fastly and is something we have to do.
--
Can we do index set splitting fastly for unitary graphs?
--
The main
--
there does not seem much point in reversing the directions of edges ala Tarjan's Strongly Connected Components algorithm. This is because, we are interested in solving Bq=0. This trivially means that -Bq=0 !!!!
So the information in the DFS info of B is contained in the DFS info of -B. Or is it? Since we have to satisfy both Bq = 0 and -Bq=0, what does the undirected hypergraph give us? Maybe nothing: We are losing lot of information by looking at the undirected hypergraph.

brings us back to the question: we should look at either Bq=0 OR -Bq=0. What additional information is present in looking at both (not the undirected hypergraph ofcourse)?
--
There are three types of nodes in the graph: the v's the w's and the e's (which are actually the edges of the hypergraph, but can be recast as vertices of the new graph).
Observation: every edge has to pass through the switch box of the E vertices.
We are looking for a cycle in this graph that passes through atleast one v in V and atleast one w in \W.
or, we are looking to remove edges that donot participate any cycle (what does this mean)?
--
Look at Cormen book for quite good notes on Shortest paths: chapters 24, 25: I am not sure what algorithm should we use for the hypergraph. Once a hypergraph has been constructed, or even the equivalent bipartite graph, the edge weights can be thought of as unit (+1). So, we may be able to do away with a Dijkstra's algorithm???? Read the rest of this entry >>

All pair shortest paths on directed graphs

The textbook algorithms for APSP assume a weighed directed graph. The algorithms are the following:

Dijkstra: basically a SSSP for each vertex: assumes no negative weight edges. running time O(V^3).

Dijkstra: better data structures: using binary min-heap: O(VE* lg V).

Dijkstra: better data structure: using Tarjan's Fibonacci heap: O(V^2*lg V + V*E).

Bellman-Ford: Also a SSSP from eaqch vertex, however, allows negative weight edges. running time: O(V^2*E) (this could be O(V^4) on dense graphs).

Bellman-Ford: improved running time

Floyd-Warshall: uses the repeated squaring algorithm Very similar to transitive closure running time: O(V^3).

Johnson: An improvement for sparse graphs. uses both Dijkstra's algorithm and Bellman-Ford algorithm as subroutines. Uses a reweighing technique. O(V^2* lg V + VE)
--

Convergence of a PDE??
equivalence of two SUREs
Predicting the final values without computation??? Read the rest of this entry >>

Arvind Sharma's book on Experiential Dimension of Advaita Vedanta

Reading the book, The Experiential Dimension of Advaita Vedanta, by Arvind Sharma.

This book is dedicated to Eliot Deutsch.



The preface itself is good. Sharma says that no word other than the sanskrit word "Advaita" is necessary to understand the concept of experiential advaita. To prove this, he claims to use only five previously unknown words in the book: Advaita Vedanta, Sankara, Ramana and Nisargadatta.

Sharma answers the question of "why is the concept of experience important or relevant" by saying that experience is something everyone can feel for themselves. This is to differentiate it from scriptural over emphasis someone may find in such an exposition.

A similar thought is given his other book titled "Advaita Vedanta", which seems to be written later. This is my post on that book (also contains the amazon link to that book). That book is divided into three main chapters: scriptural, rational and experiential aspects of Advaita. This is my post on the third part of that book.

Whose experience are we talking about? To disambiguate the term experience, as to who's experiences and which experiences, Sharma divides the term experience into the four categories:

ordinary experiences of ordinary people,

extraordinary experiences of ordinary people,

ordinary experiences of extraordinary people, and

extraordinary experiences of ordinary people.

In the introduction, Sharma says that Sankara is the leading expositor of doctrinal Advaita and Ramana is the leading expositor of experiential Advaita.

The first chapter titled "what is normal experience". At the end of chapter, Sharma raises 11 points and sub-points about how people give primacy to waking, over those of dream and dreamless sleep. This is even among among people who agree that all three are just states of consciousness and should be comparable.

In the second chapter titled "critique of normal experience" gives the counter arguments that Advaita provides to each of the 11 points and sub-points raised in the first chapter. Some significant conclusions seem to be in point 3.vi, where to answer the question 'If a contradicting experience is superior to a contradicted experience, is not waking state superior to dreaming?'. Sharma admits that a contradicting experience is superior to a contradicted experience. However all three states are capable of contradicting each other [How can dreamless state contradict any of the other? Ans: we experience pain when awake. When asleep, we donot experience it. So pain characterizes not the body but the body-consciousness as it comes and goes with it.]. For example, a rich man may dream that he is poor, which is a contradiction when he is in dream state. So, the fact that a state can be a contradicting some other state enforces our view that the contradicting state can be contradicted.

The third chapter titled "Conclusions on the critique" makes some conclusions. The important being that the three states contradict each other in terms of reality in each of them. None of these three states represents reality by itself. What is common between all three? The being I is common all three states.

The fourth chapter titled "Advaitin Experience and its relationship to Normal Experience", Sharma makes some interesting points. He answers the question, how does an Advaitin experience reality (and dualities like pleasure and pain) different from normal people. He says that

...
the realized person, however, in a sense experiences less than the ordinary person; in another sense experiences more than the ordinary person; and in another sense experiences the world differently from an ordinary person.
...

He says the following about the differences in experience of dualities by the realized and ordinary person.

The realized person experiences pain and pleasure but does not experience it in the same way as an ordinary person. ... In a sense it might be said that the realized person feels physical pain but nor mental pain. It could be said that the difference between a realized person and an ordinary person does not lie not so much in what the realized one experiences and the ordinary one does not but rather in what the ordinary person experiences and the realized one does not. The realized person and the ordinary person both experience sugar as sweet and wormwood as bitter, both see and smell and walk and talk. But the ordinary person also experiences anxiety, fear, suffering, hope, diappointment etc. These the realized person does not experience.

The eight chapter is titled "Some accounts of Advaitin Experience". It is mainly about the experience of Ramana, of his 'disciple' Paul Brunton and of Nisargadatta. [Paul Brunton wrote the book "Search in secret India". This is the Amazon link.]

Sharma concludes the book with the following:

There is starkness [emphasis mine] about Advaita Vedanta when presented in its experiential dimension. This starkness some find compelling and some repelling and others remain unaffected by it. All, however, would perhaps want to know: Does it have anything to offer?

The question was put to Ramana whose virtual nakedness symbolized, as it were, the starkness of the experiential dimension of Advaita Vedanta. He was once asked by a somwehat cynical seeker: 'Do you have anything to offer to me?'

'Yes', Ramana is supposed to have said, putting aside the comic book he was reading. 'But do you think you can take it?'

Read the rest of this entry >>

ability to multiplex - duality and non-duality

It seems the ability to multiplex thoughts seems to come naturally, except for some periods when there is a single thought. It also seems that that period of uninturrepted flow occurs only after repeatedly trying to do work and at the same time, keeping the "other" thoughts on God. This is probably what Shankara said when duality leads us to non-duality. And the Quote in PUM "The Lords's feet lead us to the other side". Read the rest of this entry >>

unitarization and directed hypergraphs: more thoughts

It is clear that unitarization results in a directed hypergraph. Also, a zero-weight cycle is a path from a vertex to itself.

Fact: if the given graph has a 1-dimensional schedule, it has one sequential loop. If it has as 2-d schedule, it has a 2-d schedule.
So, what can we say about the presence of a k-d schedule and the limits of doing something in the graph with 1 and d? (ala sandwitch theorem.)

What can we say about the presence of d-dim schedules?

Are you sure that the depth is min(n,d). Or does it have to be d? Read the rest of this entry >>

Software Pipelining and unarization

It seems that, unarization can be applied to small loops very effectively.
--
It also seems that the technique can be applied to 1-d loops and since the model is simple, maybe they can be scheduled even with resource constraints in a simple way. Read the rest of this entry >>

Siddhartha by Hesse: Final Chapter - Govinda

I have nothing to say but to redirect to the chapter "Govinda" from Siddhartha by Herman Hesse.

I am just feeling the way Sanjaya might have felt after he saw the immortal conversation between Lord Krishna and Arjuna in the Bhagavad Gita. My words would echo the same that he used in exclamation at the end of the Celestial Song.

Also the comments by Atanu on searching vs. finding are a worthwhile read. Read the rest of this entry >>

Atri-DattaAtreya and Vyasa-Suka: a comparision

Both Dattaatreya and Suka are sons of well known sages in Hindu puranas. The concept of son itself has a hidden meaning, as in other familial ties. A son ofcourse carries forward the school of thought that the father propagates, which is exactly what these two great sons did.

Dattaatreya is the son of Atri Mahamuni. The name of the sage Atri itself -- A-tri: without three or beyong three -- conveys the spirit of one who has transcended the three levels of consciousness (not just beyond the three characteristics of Sattva, Rajas and Tamas). Datta-Atreya means, someone who has been adopted by such a sage and AnaSuya, one who is beyond Asuya. It is said that Brahman himself had been Datta (taken as a son) by such a couple. Datta-Atreya is said to be the sage who formulated the basic concept of Advaita: namely, Aham Brahmasmi (Thou art Brahman).

Suka is the son of Vyasa. Vyasa is the divine sage who compiled the vedas and wrote the Mahabharata containing BhagavadGita and VishnuSahasranamam. Vyasa literally means the divisor of vedas. Suka is known to be his son, who had transcended all the stages of consciousness from birth itself. Suka narrated the Bhagavata Purana. The narration has well known chapters like Gajendra Moksham, Prahlada Charitam, where he not only conceptualized the method of Jnana (like the original prayer to nirguna Brahman by Gajendra) and of course, the method of Bhakti (where else but the pinnacle: chapter 10?) in the story of Lord Krishna.

An Anecdote about Suka: It is said that Suka if he heard even the name of Radha, would go into samadhi. So, in the whole Bhagavatam, there is no mention of Radha-Devi. The questions put forward by Parikshit were such that no mention of Radha could be made by Suka when he was answering the story.

It seems that the Atri-Dattaatreya are more abstract to understand by ordinary human beings. (This is even though the teachings are very simple, like the 24 natural gurus of Lord DattaAtreta.) So Vyasa-Suka had made the ideas into a form that is more concrete, and possibly easier/simpler in another way. The result was a concept of Bhakti which could be understood by the multitudes.

It should however, be not be forgotten that the Avadhuta in the Avadhuta-Yadu samvadam, which occurs at the end of Bhagavatam, is none other than DattaAtreya. So by inserting that dialogue in a later chapter of Bhavatam, Vyasa-Suka made the wonderful reader-friendly assumption that a reader who has read/listened to Bhagavatam till that chapter is sufficiently mature to understand the Advaitic concepts of DattaAtreya. Read the rest of this entry >>

checking for the validity of a transformation on unitary graphs

Given a d-dimensional vector and a computation on the vector, what are the problems that can be solved fastly? If we are also given that the dependence components in the associated computation are from the range {-1,0,+1}, can we find the equivalence of two computations? If so, give an algorithm to find the equivalence fastly.
--
If the size of the computation is so smaller than the size of the array, we can do a reachability analysis and make the calculation fast.
--
Given: a single d-dimensional vector and a two loops of dimensions n1 and n2.
--
What if we annotate a point in the data dependence graph by the function at that point?
Do it for 2-dimensional and then 3-dimensional arrays.
--
Given: two polytopes, P1 and P2, of n-dimensions and one polytope P3 of 2d-dimensions (which we will call the tile polytope: given a tile size, we have an polytope.)
The input to each polytope is a the same facet. The output of the 2n-dimension polytope.
--
Given: two alpha programs with the following characteristics
---------
Program1:

an parametrized n-dimensional polyhedral domain.

A statement defined in all the points of the domain.

A monodimensional time schedule, which is valid.

A memory mapping
---------
Program2:

A parametrized 2n-dimensional Z-polyhedral domain. The domain can be expressed as a affine transformation of the original domain.

A collection of statements defined in all the points of the domain

A mono-dimensional schedule, which is valid (define the schedule function)

A memory mapping, which is an affine function of the one in program1.
-------------
Verify that the two programs do the same computation. Can it be done? Can it be done in a fast way?
So the statements and variables in Program2 are of two types

1. ones that correspond to variables in program1.

2. ones that are additional variables (the buffers).
Consider the following situation. If we remove all the variables of type (2.), from program 2, then we are left with a memory mapping that is "similar" to the one in program1 and ofcourse, it has similar schedule to the one in program1. define similarity.
--
Simple question: prove that the transformation is right.
easy first step: give a transformation from the original n-d space to the transformed 2n-d space and also the reverse of it.
Let the orig space be I_n. Let the tile sizes be S. The 2n-d space is given by T .................
--
What are the representations of a Z-polyhedra? Read the rest of this entry >>

hardness of the URE/SURE scheduling

The input to a SURE scheduling problem is a (n+d)*m matrix, and we are to find the minimum running time of the system (with a reasonable aggrement on this statement).

n has to be >= 1.

If n=1, then we have a URE. The scheduling problem for n = 1 is as hard as the LP problem of d*m size.

When n>1, the problem is harder.

OTOH, d has to be >= 0

If d = 0. we have a digraph and the scheduling problem is a DFS!

if d = 1, we have a digraph, whose weights are scalars. This means that the scheduling problem is as hard as a APSP.

for d > 1, the problem becomes harder Read the rest of this entry >>

A data structural approach to detect cycles

Refer to the previous post about the construction of the hypergraph with ordinary nodes and hypernodes.

The ordinary nodes correspond to the number of times an edge has been selected in the PRDG. A hyperedge is from a subset of (ordinary) nodes to a subset of nodes. Either the head of the edge, or the tail of the edge can be a zero size subset.

Now define the arity of a hyperedge as the sum of its indegrees and outdegrees.
Some simple observations:
for a hypernode v with an edge S to T, if indegree(v) = outdegree(v) = 1 (or card(S)=card(T)=1), then we can "club" the two singleton sets to make another singletonset. The hyperedges which begin or end at the vertices of the sets S and T can be made to correspondingly begin or end at the new vertex, which can be called its own singleton set.

The hypernodes can be stored in a priority queue, which supports the following operations:

deletion of the hypernode with the minimal arity

Also, a hypernode v such that indegree(v) = 0 or (outdegree(v) =0) can be removed from the queue. This would lead us to a pruning of the graph:
removal of the hypernode from the priority queue: This hypernode may not be at the top of the priority queue.
pruning the hyperedges which begin or end at these vertices
--
TO DO: try to see some examples of the particular linear programs of unitary form.
solve the dual linear programs
look at the original and dual graphs Read the rest of this entry >>

transitive orientations and separating hyperplanes

Given the unitarized block matrix of size (n+d) rows and m columns, we can draw a hypergraph G with (n+d) nodes and m edges in the following way:
(How can you use Euler's theorem in these proofs?)
The PRDG has no self loops. They can be eliminated in a simple way.
---------------------------------------------------------
====================
Alg1: Algorithm to construct G
====================
For every row of the block matrix, there is a node in the hypergaph /*There are total n+d nodes in G*/
for all columns of A, do the following:
If there is a +1 in a column of G, then we make them the tail of a hyperedge. If there is a -1 in the row, we make that corresponding node a head of a hyperedge (A 0 does nothing. By a restriction in the input PRDG, a 0 in the incidence matrix of input PRDG corresponds to nothing).
---------------------------------------------------------
We can construct another graph G' in the following way:
---------------------------------------------------------
====================
Algorithm to construct hypergraph G'
====================
Notation:
The input PRDG is unitarized by step A_1 of the algorithm (given above). So in the rest of the paper, we refer to the unitarized-PRDG G_u simply as a PRDG. We also refer to it as a graph when the context is clear (In such instances, we refer to the other graph as a hypergraph). We also refer to the PRDG in terms of its block matrix. The block matrix is a (n+d)*m matrix, with the columns corresponding to its edges. Also, the top n rows corresponding to the incidence matrix of the PRDG, which is but a directed graph. The bottom d rows of the block matrix contain the d-dimensional dependence vectors associated with that corresponding edge.

G': A hypergraph constructed from the PRDG. Specifically, it has

a node for each column of the block matrix A (or, a node for each edge of the PRDG)

a hyperedge for a row of the matrix A. This also means a hyperedge which for a vertex of the PRDG and a hyperedge for each component of the dependence vector. The tail of the hyperedge is all the rows of A that have an entry equal to -1. The head of the hyperedge is all the rows of A that have an entry of +1.

one hypernode per hyperedge of the hypergraph G': These are the additional nodes that comeup in the analysis. Refer to section ... for additional notes on types of hypernodes.
---------------------------------------------------------

Lemma 1: G'=COMP(UNDIRECT(G))G' is the graph obtained by the complementing the underlying undirected graph for G(see proof below).

Lemma 2: In graph G, all the hypernodes are either sources (all outgoing nodes) or sinks (all incoming nodes).
Proof (by construction):
Corollary: in graph G', for v \in hypernode, indegree(v) = outdegree(v)

Theorem: The given system of equations has a solution iff the orientation of G is a transitive orientation.
Proof(if): The orientation of G is a transitive orientation

Corollary: The given system of equations has a zero cycle iff the orientation of G' is a transitive orientation.
--
What is a separating hyperplane? How to do decomposition?
--
the given PRDG has atleast one alternating sign in every row and column.
--
Dependence analysis of unitarized PRDGs Read the rest of this entry >>

separating hyperplane for an n-dimensional unitary polytope

From sci.math on 13-JUL

Why don't we just say "polyhedra" instead of saying "convex polyhedra"? Isn't every polyhedron convex by definition(an intersection of affine
halfspaces)?

A poster replied

Well, it's really a terminology issue. Some people don't consider polyhedra convex. So for example this person's site: http://www.korthalsaltes.com/ has lots of non-convex polyhedra (eg: great icosahedron).
But yeah, in discrete geometry the definition necessitates convexity.

This is the link.
--
Frame the question of ZCD in terms of the polyhedron. Frame a version of Farkas lemma for the type of polyheda. What does the unitary polyhedron mean geometrically. What does its dual mean?
--
Draw the vectors in the (n+d) dimensional space.
--
Approach by paths on hypergraphs.
--
Given a colletion of hyperplanes, all of which pass through the origin, find if there exists a second point which lies on all the planes. Applying a variant of Farkas lemma(version II in ziegler's book), this question is equivalent to finding if there exists a row vector c in m-dimensional dual space with cA >= 0 and c < 0.
--
What does it mean by saying that there exists a vector c which has a positive dist with every column of the {0,-1,+1} matrix A?
get the farkas lemma for separability. Read the rest of this entry >>

directed hypergraphs and MDS scheduling

Assume we have unitarized the PRDG. Also, there exists no self-loops (A zero means no edge. That's it). We obtain a (n+d)*m matrix. What if we interpret this as a directed hypergraph?
--
We are looking for a cycle, the edge weights of which sums to zero. So does this map to the presence of a cycle in the new model?
A simple example with 2 vertices and anti-parallel edges of weights (1,-1) and (-1,1) shows a cycle in the new graph. What does this mean?
Are we asking for an APSP in hypergraphs?
We are looking at a type of graphs called directed hypergraphs. Call them DHG. How is a DHG represented? Show figures of the representation.
Found the tutorial paper.
--
Does this mapping from PRDG to DHG map to detection of cycles in the new graph?
Define a path and cycle. B-arc, F-arc.
We can do a DFS and assign to each vertex a DFS number.
--
To do: make examples and check them, especially the ones similar to KMW.
What does MDS mean? coloring?
--
Call as fictitious nodes, nodes that correspond to the bottom part of the block matrix. Cycles which involve the fictitious nodes donot seem to matter. Classify this statement.
Statement of the zero cycle detection: begin at an "actual" node and do a DFS. If we reach a node back, then we get to a cycle. Is this right?

--
To do: read how does a DFS detects cycles: types of edges: tree edges, back edges, cross edges and forward edges.
--
did some part of DV-KMW-EX.
A "ZC" should touch both the original vertices and also the new vertices.
Partition the nodes into actual nodes and dist-nodes (call them D-nodes). A ZC in the PRDG should touch both nodes and D-nodes.
--
Group the nodes into the G-nodes and D-nodes. If there exists a cycle which has at least one node from G-set and atleast one node from D-set, then we have a zero-cycle in the original PRDG. Mark a hyperedge e (u_1...u_i -> v_1...v_j) as dashed if u_k (k \in 1..i) \in G-set and v_l (l \in 1...j) \in D-set. Or otherwise.

Look up the definition of Hypergraph from here. Also, get the definition of dual of a hypergraph, among other definitions.
This is a restatement of the Farkas lemma.
--
Modular Memory allocation: fibonacci example. Read the rest of this entry >>

semidefinite programming and MDS approaches

There are many ways in which we can approach to formulate the ZC-D or MDS using SDP. Here are the approaches for ZCD.
Method1: Begin with an approach similar to the LP formulation. define a diagonal matrix X such that diag(X) = x, where x is the x of CM-Z (or q of DV-KMW) To recap, x in CM-Z determined the number of times an edge is taken in a ZC. Also define (n+d) diagonal matrices A_k such that diag(A_k) = Kth_row(A), where A is the same as A of CM-Z (or B of DV-KMW). Just to recap, A in CM-Z had as the first n rows, the incidence matrix of the graph and has as the next n rows, the d-dimensional weight vectors associated with the edges.
The resultant "SDP" is the following:
-------------------------------
min X
s.t
A_k @ X = 0
forall k = 1...d
where A_k and X are all diagonal matrices.
//A and X belong to M_(m)
-------------------------------
Method2:
min X
s.t A_k @ X >>= 0
forall k = 1...d
where A_k is the adjacency matrix of the kth component of the dependence components.
This method raises many questions:
A_k is not a symmetric matrix. Can we make it a symmetric matrix, using a discrete Lyapunov kind of equality?
What does that mean for the matrix X??

--
To Do:Look up the spectral graph theory book to find how weights on the edges are represented.
What is the meaning of the eigen values of a weighed directed graph? How do you interpret it with respect to any of the known graph algorithms? Read the rest of this entry >>

more semidefinite programming

The zero cycle detection from a graph can be done by a single LP program. Same as the one in CM-Z. So it can trivially be made a SDP.
----------------
The original LP is
min 1*x
s.t A x = 0
0 != x >= 0
---------------
The "SDP" would be
min I*X //I is a unit matrix of size n*n. X is a diagonal matrix of size n*n
s.t A_i . X >>= 0 for all i = 1..nrows(A) // A_i is a diagonal matrix such that diag(A_i) = i th row of A. Also, >>=0 is the relation for SEMI DEFINITE
0 != X >= 0
----------------
Since this conversion is trivial, what can we do something more clever?
How can we schedule the points using SDP?
to do: read lovasz''s notes. Vazirani's chapter. chapter from complexity-approximation. See if SDP is covered in Schrijver's new book.
--
Start with the example in CM-Z
--
Zero-cycle and eigen values/vectors: Zero cycle equation is Ax=0. Compare this with the eigen value equation Ax=(lambda)x. This means that, for a graph with zero-cycles, the eigen values are 0. Is this right? Also it could mean that all the eigen vectors are the zero vectors. What coule be a better classification?
--
Approach1:
What happens if we actually take the ZC equation and solve it for eigen values?
Two problems: (1) The block matrices are not necessarily a square matrix. Suppose, for now that we add additional edges/nodes so that we make it a square it.
(2) The block matrix is certainly not symmetric. This is not a big problem, as it will just lead to complex eigen vectors.

Approach2:
The usual method
From the block matrix, we can make the following observations.
The top part of the block matrix just represents a path in the directed graph. The bottom part represents the weighed sum of the components of the dependence vectors (i.e., the weighted sum of the first component of all the dependence vector, weighted sum of the second component of all the dependence vectors etc).

Top part.
--
to do What does it mean by the trace of a directed graph? Given that we need a square matrix, should we look at the adjacency representation, rather than incidence matix representation?
The important question may be, what does the zero cycle path mean in terms of the eigen values/eigen vectors?
--
Think of a directed graph represented as an adjacency matrix and each non-zero element annotated by the weight of that particular edge (the weight could be a d-dimensional vector). Now, formulate the problem of zero cycle detection in this matrix.
We have to find a n*n matrix X which has non-zero entries when that particular edge is "touched" in a zero-cycle. Further, the non-zero entry is equal to the number of times that edge is touched. Given a matrix X like this, it is easy to detect the zero-cycle (find the directed MST?).
--
Both the self-loops and multiple-edges can be removed by a simple method of addition of fictitious nodes and edges. We are left with a simple graph (not multi-graph) which has all 0's in the adjacency matrix. Let us call such a matrix A.
Let us call as X, a n*n matrix, which will have a non-zero element in the element (i,j) iff the edge between vertices i and j is a part of a zero-cycle. Are we minimizing the program? How do we schedule it?
Now is the matrix A semi-definite? What does the following mean X >>= 0?
define the definiteness of a directed and undirected graphs.
--
Define a directed graph, whose edges are annotated with scalar weight edges. What can we say about the SDness of the adjacency matrix?
--
The spectrahedra of an undirected graph has been well studied. What about the spectrahedra of a directed graph and what about the eigen values of the graph.
--
Since we are starting with matrices whose diagonal elements are zero, what can we say about the eigen values of each matrix? There are no self-loops => the diagonal elements of the matrix are zeroes => the coeff of the (n-1) term = a11+a22+a33+... = 0. Also, ...
--
Look up the relationship between unitary PRDG's and Hadamard matrices . Look it up in Stanley's book and Knuth.
--
min X
s.t A_1 @ X >>= 0
A_2 @ X >>= 0
A_3 @ X >>= 0
...
A_d @ X >>= 0
X >>= 0
--
Now, A_i can be thought of as the adjacency matrix of the PRDG, which is a directed graph, annotated by the weights of the ith component. It has no self-loops. This means that its diagonal elements are zeroes. So the trace of the matrix A_i is zero. It is called a trace-free matrix(see the link trace link). This is because of the property of the characteristic polynomial induced by the matrix A_i. A property of trace states that tr(A@B) = tr(A^T B)
--
the link on Characteristic polynomial is nice.
Question many things seem to depend on the positive definiteness of the matrix A_i. How can we prove that it is positive definite? If it is not +veSD, can we apply a transformation to th PRDG so that the resultant graph is +veSD?
Question is What can you say about the \lambda_min of a directed graph? What can you say about the definiteness of a non-symmetric matrix? In particular, a matrix whose trace is zero?
--
According to this link

Most of the eigenvalue optimization theory has been developed for real, symmetric matrices. It is known that such matrices have real eigenvalues. Unsymmetric matrices, on the other hand, have complex eigenvalues in general. It is possible, however, to translate the constraint on the real part of the eigenvalues of a real unsymmetric matrix (say A) to be negative, into a positive definiteness condition on a real symmetric matrix (P) through Lyapunov’s matrix equality (2). Since it is a sufficient and necessary condition for a real symmetric matrix to be positive definite, its eigenvalues to be positive, the condition on the eigenvalues of the "difficult" unsymmetric matrix A is translated into another condition on the eigenvalues of the "not-so-difficult" symmetric matrix P. In order to avoid the potential non-smoothness arising in eigenvalue optimization, interior-point / logarithmic-barrier-transformation techniques have been successfully applied (Ringertz, 1997). For a comprehensive reference of interior-point optimization, see Fiacco and McCormick (1990). Making use of logarithmic and matrix determinant properties, it will be shown that the potentially non-smooth constraints on the eigenvalues of matrix P may be expressed in terms of the determinant of matrix P, which is a smooth function of the optimization variables.

The Lyapunov's matrix equality happens to be the following
Matrices A, P and Q are related through Lyapunov’s matrix equality. Read Lovasz's notes on the same. What does it mean for a directed graph? How can you "make" a undirected graph which is equivalent to it?
According to the Horn's Topics in Matrix analysis,
GA + A*G = H is the Lyapunov;s equation. (A*: means skew-hermintion not transpose: check)
It says that A is positive stable iff there exists a +veSD G of size n*n and H is +ve definite.
Hurwitz matrix
+ve cycles and stability of systems are equavalent!!!!! Read the rest of this entry >>

unitarization: a tiling approach

If the dependences in the original PRDG are uniform, the dependences in the tile graph are unitary (from the range {-1,0,+1}). Further, the dependence components are all from the range {0,+1}. Also, the tile graph is a URE, as all nodes are of the same "type". (Check if these statements are true for all tilings.)

Some assumptions are (1) There are a large number of tiles, in any dimension (if there are non-zero number of tiles in that direction, that is) and (2) Each tile has large number of iteration points. What about the boundary points?

So, this means that we have two PRDGs: The (1) URE of the tile graph and the (2) SURE of the iteration points inside a tile. Note that each of these are *much* smaller than the original PRDG. However, we will assume that their number is still large so as to consider the mode. This means that if we begin with a 2-d square iteration space with 1000*1000 points and divide it into 10 tiles of 100 points each. We still have to deal with a 10*10 points in the tile space, that is 100 tiles. Also, a tile has 100*100 points and so has 10000 points. Each of these is a considerable number.

We need to take care about the boundaries of the tile.

All this might lead to a ratio of the following. time taken by a free schedule of the tile graph and time taken by a free schedule of the original PRDG.

We also might add some models. That could make the problem harder.
--
Now we have an agreemnent on the following model:
(1) Define a URE with edges corresponding to the dependences between different tiles. It also has some parameters (which define the number of iteration points inside a tile).
(2) Define a SURE which is parametrrized by some variables defined in problem (1). Now this SURE could be non-infinite.

Question is: what can you say about the computability/scheduling of the combined system?
--
to do: read mails around march end
--
questions/answers from meeting on 07/14:
memory optimization: pareto optimal for memory and schedule. there is no "better" point, because of the multi-criterion optimization. We are talking about the solution space, not the feasible space. The set of interesting solutions form a curve. North-east, south-west points..
--
objections to using SDP for one-shot scheduling. the multi-dimensional schedule operates in a way that the output of the solution at one point is given as input to the next LP program(is this as simple as some edges disappearing?) If we want to use a single program, possibly that is an SDP, what do we minimize?
Right now, with LP formulation of the MDS, there is no way that we can compare two schedules (what does this mean?) with different number of dimensions. We can only compare the schedules of same # of dimensions.
So, we frame the scheduling problem as a polynomial schedule.
--
When is a polynomial representable as a SDP? The set seems to be called semi-algebraic sets. Read the rest of this entry >>

semidefinite programming for multi-dimensional scheduling

The mono-dimensional scheduling problem can be solved by a single linear programming problem. The multi-dimensional scheduling problem, however, requires multiple calls to the LP solver. The minimum number of LP calls is in the paper DRV-KMW. Can ZC be detected by using a SDP solver? Can MDS be done by a SDP solver? The latter is a harder problem as it also has to return the certificates (the rows of the schedule).

Fact: An edge can be on only path of the KMW-T. If it lies in a prime node, then there exists a ZC.

The scheduling matrix, can be constructed in other ways, like using KMW method (one LP call per edge) or KS method (n*logn LP calls).

To Do: Weak separation oracle from Lovasz's lecture notes (and also GLS:Grotschel-Lovasz-Schrijver book?). How to add quadratic constraints still preserving semidefiniteness.
--
SDP duality holds only under some regularity conditions. What are they?
--
To Do: SDP in mails
--
A Linear program is trivially a SDP. If a constraint of a LPP is of the form <= p, we can define a diagonal matrix A with A_i,i = a_i and we can also define a variable matrix X_i,i = x_i The resultant program is a SDP.
--
We could do a similar thing with the vectors q or X. What about the vector (1,-1) for the edges? The 2nd eigen values are non-+ve. which means that we cannot directly use that value. However, SDP only requires that the variable matrices are SD. not their coefficients.
--
Is this a SDP?
max sum_e z_e
z^2 <= 1
--
To do look up the different SDP formulations from Lovasz's notes. Read the rest of this entry >>

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? Read the rest of this entry >>

separating hyperplanes, certificates, Ziegler

Main idea of CM-Z: Computing a certificate (a weakly separating hyperplane) and then computing the partition of the graph (by an All Pair Shortest Paths).
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

theorems of the alternative

transposition theorems

duality theorems

good characterizations

certificates for validity

separation theorems
--
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. Read the rest of this entry >>

separating hyperplanes, memory allocation

QR say that for a given schedule, the projective memory allocation method gives the minimal amount of memory required.
--
What can we do with the separating hyperplanes to minimize the amount of residual memory?
--
The general approach to solve the ZC detection problem: Compute a separating hyperplane called a certificate (using a LP in the case of KMW, KS, DV-KMW or a faster way as in CM-Z) and use the certificate to partition, or decompose, the graph. CM-Z say that the depth of the decomposition tree is bounded by the dimensions of the weights. Should it be n? no. It should be min(n,d).
--
More about QR memory allocation: Darte and others have also proposed a memory allocation algorithm. Their paper, DSV-LM has a nice overview of QR.
--
To do: QR has a nice overview of the scheduling problem in general. Read it. Read the rest of this entry >>

separating hyperplanes for unitary graphs

Taking the clue from CM-Z about the ZC problem into, (1) finding a hyperplane that separates and (2) partitioning the graph using the hyperplane, we solve the problem (1) in faster time, using an oracle.
--
Theorem on convex polytopes: Two closed, convex, disjoint sets can be separated by a hyperplane.
Yes, but how to find in fastly when the distances are in the range {-1,0,+1} ideas: do a recursive separation?
--
Important theorem on convex polytopes: A convex polytope is the sum of a polytope and a cone.
--
When we unitarize, we get some kind of patterns in the incidence matrix(top part of B). What is it?
--
Questions about KMW-EX-577: What is special about edges e2 and e4, the ones from v1 to v2 and back again? What makes them disappear? How are they weakly connected? What makes edges e1 and e3, the self loops, stay? When we draw the vectors on a 2-dim hypercube, which happens to be a square, e2 and e4 are parallel (anti parallel to be precise) and are the maximal number of vectors that can form a ZC. Is this because, we are maximizing the the set of vectors that can stay for next level of decomposition?
--
Construct an example where there are 2 edges which are antiparallel in one direction like {(1,-1),(-1,1)} and another set of edges (say 3) which are anti-parallel in another direction like {(1,1),(-1,-1)(1,1)}. What will the KMW return?
--
KMW notes: page 586-587, example 10, fig9 and page: 587, example 11, fig-10. KMW generate two schedules, the free schedule and smoothened schedule.
--
To do: Write the duals of the KMW-EX and get the polygons.
To-do: Prove Conjecture: get the hyperplane which passes through the origin and is parallel to the maximum number of hyperplane. This vectors that are not parallel to this hyperplane are weakly connected. So, It seems that a sort (bucket sort?? in linear time???) of the dependence vectors invariant to the a change of sign, which means that (1,-1) and (-1,1) map to the same bucket, is all is required.

To do: Verify conjecture for a two PRDGs: one that is easy to reason and one that is complicated that the algorithm finds one.
--
When we look at the columns of the matrix B and ask when are two columns linearly dependendent and how can you maximize the dependent edges?
-- Read the rest of this entry >>

Unitary graph zero cycle detection

We can unitarize a PRDG arbitrarily, so that all the components of the graph are from the set {-1,0,+1}.

In 2-dimensions, all the edge weights have been mapped to the 9 points on a unit square.
--------
1 2 3
4 5 6
7 8 9
-------

Now point 5 does not add to the weight of any cycle.
Call the points (1,4,7) as -ve-red, call points (3,6,9) as +ve-red
Call the points (7,8,9) as -ve-blue, call points (1,2,3) as +ve-blue

--
To do: Look at the examples in KMW
--
unitarization may not be necessary, if we somehow convert a distance vector into into its angle represented by a value on the unit-hypercube and magnitude represented by ????????????
--
In higher dimensions, we can consider the 3X3 matrix, with some less number of nodes as base case and properly split graphs of large number of nodes, edges and high dimensions.
--
To Do: do a search for fast linear programming algorithms when the matrices are unitary. May want to search for linear programming unit cost etc...
--
Imagine the graph annotated by the the vectors. Now Decompose the components into atmost two components, each is from of 2,4,6,8. Remove the edges which donot have components that influence the components on another side.?????
--- Read the rest of this entry >>

Arvind Sharma's Experiential Approach to Advaita Vedanta

The third part of the book covers Advaita Vedanta in an Experiential approach. Sharma asks, why an experiential approach? Are not the usual scriptural and rational approaches enough? He answers the question, giving an example of the the three states in which human beings can exist are waking, dreamin and deep-sleep. It seems that the
scriptural approach ==> deep sleep
rational approach ==> waking
experiential approach ==> dreaming state

If you ask most people, to group two of these as close together and the third as different, most people would give the configuration {waking}, {dreaming, deep-sleep}. This is because, the states in the second set are "without activity". Advaita notes that the following division is more appropriate: {waking, dreaming}, {deep-sleep}. This can be substantiated from the famous examples from Janaka dreaming that he was a beggar. Tzu dreaming he was a butterfly. Incidentally, it was Chuan-Tzu, not Lao-Tzu who dreamed so. He is said to be second only to Lao-Tzu as a representative of Taoism. Read the rest of this entry >>

Arvind Sharma's book on Advaita Vedanta

Reading the book "Advaita Vedanta: An Introduction" by Arvind Sharma. The Amazon link is this. In the book, he takes a simple introductory approach to the subject. The book seems a little verbose at places, but has summaries at the end of large paragraphs. It may be useful for someone to read this book prior to reading to Deutsch's rather terse book(Amazon link). Arvind Sharma takes a tri-fold approach to explain the concept of Advaita Vedanta: They are (1) the Scriptural, (2) the Rational and (3) the Experiential approach.



Shri. Sharma, in the introduction of the book, begins by stating that both philosophy and religion try to pose the fundamental question "What is real?"
The book begins with how the Hindus wanted to attain liberation in this world itself (jivanmukti) rather than, postponing it to a later time, either death or on the judgement day, as in Christianity and Islam.

The introduction explains the six systems of Indian philosophy nicely. My notes from Dasgupta's book on the same subject is here. Both agree nearly. Sharma orders the astika systems as (Nyaya, Vaiseshika), (Samkhya, Yoga) and (Mimamsa, Vedanta). The first pair, he notes, are closer to naastika systems, while the second pair accept Vedas a-posteriori. Sharma also notes that Mimamsa and Vedanta take a very close approach to how the Vedas are interpreted, i.e., both the schools base themselves on the Vedas. They are based on the "anta" part of the Vedas. Though, as in some other religions, Hindus accept that the Vedas were received, Hindus also recognize the limitlessness or infinity of Vedas. This also means that Hindus attribute no specific time or place or persons -- either cosmic or human -- for the "receiving process" of the Vedas.
Also he explains the four parts of each Veda as (i) Mantras or Samhitas: the hymns in praise of gods, (ii) Brahmanas: the prose explanations of the ritual use of these hymns (iii) Aranyakas: reflections on the significance of the ritual and (iv) Upanishads: Secret texts meant to communicate the highest mysteries which go beyond ritual into the realm of spiritual knowledge.
In the explanation of the first Mahavakya Aham Brahma Asmi (I am Brahman), Sharma nicely notes that though everything "is" Brahman, the way in which Maya (or the universe) "is" Brahman is not the same as Atma "is" the same as Brahman.

The conclusions has the following translation of the famous verse on the main tenet of Advaita:

The non-duality of the Brahman,
The non-reality of the world
and the non-difference of the Atman from the Brahman
These constitute the teachings of Advaita

Considering that one of Mr. Sharma's books is dedicated to Eliot Deutsch, It is surprising that the book does not to cite Deutsch's book.

On another note, Arvind Sharma's experiential approach to Advaita seems to be unique and special. This is partly because, one of the primary questions of Advaita is "What is Real?". This question has to arise in the seeker's mind, after he feels that some of his experiences are not real!

A reader on the advaitin mailing list had recommended strongly, the book "The Rope and the Snake" by him. This is the Amazon link.

Read the rest of this entry >>

depth of KMW-T and oracles

Suppose an oracle tells us that the depth of the KMW-T is 1. How can we verify that? by finding the witness vector or separation vector. which one??
--
If we generalize the idea of the oracle further and say that we can verify in some time T \in POLY(n,m,d,max-distance), whether the KMW-T has depth is k or not. Suppose an oracle tells us that the depth of the KMW-T is <= k. A (binary?) search across k would give us the certificate to verify the statement. This would take the running time of the algorithm to be T * log k. How can we do better?
--
to do:

Get the definitions of witness and separation vectors (of various kinds).

understand the concepts of independent sub-space and maximal independent subspace.
--
Prime and composite nodes: In the previous post, there were a couple of analogies between the different decomposition trees. Let us call a leaf of a decomposition tree prime, if it is annotated with a component which is a node of the original graph. Otherwise, call the leaf as composite. The whole problem of ZC-detection is but seeing if there exists a composite node.
--
Define an edge casting a shadow on another component if the edge is in the maximal independent subspace of the component????? So, can we begin with a node and keep adding edges to it till we detect a ZC?
--
To do: get the idea of maximal independent subspace and difference between the witness and certificate of CM-Z.
--
Top-down decomposition Vs. Bottom-up construction: How to unify two components?
--
To-do: understand the KMW-EX with depth of 1 and 2. how and why are the depths of that size.
to-do: frame a LP program which takes a two connected components and returns a parent node with a certificate. Suppose we want to add a third node which is in the same strongly connected component as these two, it need not have a parent which is different from these two. It can be attached to the same parent as the original. The certificate stored at the parent may or maynot change.
--
The KMW-EX -577 is very useful to know about the longest paths. Visalize a bounding box, with nodes of two colors and the dependences. If there is a circuit in G^\infty, there is a loop in the PRDG.
--
The memory optimization by building through subspaces and simultaneously increasing the "range" of subspaces. Read the rest of this entry >>

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? Read the rest of this entry >>