Berge: Theory of Graphs

It seems that the concept of incidence matrix was started by Kirchoff.

Representation of a graph: A graph can be represented as a pair (X,Gamma) or (X,U). Gamma is a function from X -> X. This encodes multi-graphs and infinite graphs (if we allow Gamma to be a multi-function). U is a subset of the possible arc sets. If U is a symmetric set, then the graph is undirected.

Chapter 3

Core concept: bounded is different from finite. Finite is different from infinite.

If a set has bounded number of elements, its cardinality is finite and not infinite.
If a set has unbounded number of elements, its cardinality could be finite, or infinite.
If a set has finite-unbounded number of elements
A good example is the 1-d graph which starts at origin and extends unboundedly towards right. Each node on the graph has edges to its immediate left neighbour and all the nodes to its left. For such a graph, the outdegree of any given vertex is unbounded. Still it is finite!!!

Also, a set could have unbounded number of elements and still be finite.

Finite Graphs: A graph is called finite if |X| is finite.

[If there exists a function that maps a vertex of the graph to a natural number, then the graph is not finite. Further, it is an infinite graph. Also, there seems to be many types of infinite graphs. However, Berge gives talks about certain types of infinite graphs meaning ones that satisfy some conditions, esp. the early theorems so that the results of finite graphs can be extended to those types of infinite graphs.]

Gamma-finite: A graph is Gamma-finite, if Gamma(x) < inf for all x in X. (This means that every vertex has finite number of edges out it.)

Gamma^-1-finite: A similar definition about Gamma^-1 rather than Gamma (Gamma^-1 is the inverse of the function Gamma.)

A graph is called locally finite if it is both Gamma-finite and Gamma^-1-finite. Also, a finite graph is locally finite.

Gamma-bounded: A graph is said to be Gamma-bounded if there exists a m such that Gamma(x)<=m for all x in X.

Progresssively finite: A vertex v is progressively finite if no paths of inf length start at v. A graph is progressively finite if is is progressively finite at each of its vertices. [see a note below about progressively finite and having no circuits.]

Progressively bounded: A graph is progressively bounded at vertex v if a number m exists such that the length of all paths starting from v is less than or equal to m. A graph is progressively bounded if it is progressively bounded at each of its points.

The relations regressively finite and regressively bounded are similar to the definitions of progressively finite and progressively bounded. The later deal with the graph (X,Gamma), while the former deal with the graph (X,Gamma^-1).

Relevant examples

RDG: An RDG is a finite graph. So it is Gamma-finite and Gamma^-1-finite. It is also Gamma-bounded and Gamma^-1 bounded. It is usually has cycles, as we deal with a strongly connected component of the RDG. So, it is not progressively bounded. Neither is it progressively finite. It is also not usually regressively bounded and not regressively finite.

EDG of a RDG defined across a finite domain: Such a graph is a finite graph. It is also Gamma-finite and also Gamma^-1 finite. It is also Gamma-bounded and Gamma^-1-bounded. It is progressively finite, if its associated SURE is computable and there exists a schedule. It is progressively bounded if the SURE has a bounded schedule. What about regressively bounded and regressively finite???

[actually the graph theoretic definitions preceed the definitions of computability and schedules. Here we will allow circular definitions.]

EDG of a RDG defined across the entire positive orthant: Such an EDG is an infinite graph. It is Gamma-finite and also Gamma^-1 finite. It is also Gamma-bounded and Gamma^-1 bounded. It is not progressively finite and so is not progressively bounded. It is also not regressively finite and so is not regressively bounded.

EDG of a RDG of a SARE defined over a finite domain: Such a graph is a finite graph. It is Gamma-finite, Gamma-bounded and so Gamma^-1-finite and Gamma^-1-bounded. It is progressively bounded, and progressively finite. It is regressively bounded and regressively finite.

EDG of a RDG of a SARE defined across the entire positive orthant: Such a graph is not finite. It is not Gamma-bounded. Neither is it Gamma^-1-bounded. It is Gamma-finite and Gamma^-1-finite.

I donot know about the computability conditions of either of the types of SAREs. So, no statements about the progressively.* and regressively.* for now.

Theorems

Theorem 1: If a graph is finite, the properties progressively finite, progressively bounded and 'without circuits' are equivalent.

[Note the implication of 'without circuits': If a graph is finite and it is progressively finite, it cannot have any circuits, as that will lead to having infinite path lengths beginning at any of the vertices participating in the circuit. A similar statement can be said about the progressively boundedness of a finite graph.]

Proof of therorem 1: Direct from applying the definitions to a finite graph.

[This proof is kind of easy, because, for a finite graphs |X| < inf. Also, if it does not have any circuits, there exists a bound on the maximum length of a path from each vertex. So, the graph is progressively bounded and is trivially progressively finite. As Berge himself says, infinite graphs are more interesting.]

Questions on the wording of theorem 1: Theorem 1 talks about the equivalence of 'progressively finite' and 'without circuits' for finite graphs. When are the properties not equivalent for infinite graphs?

[which of the 'progressively finite', 'progressively bounded' and 'without circuits' implies the other? It seems that 'progressively finite' combined with 'the graph is finite' is enough. The other two properties seem a little too strong.]

Answer: My current answer is the following: It does not seem that we can give a statement about all paths of an infinte graphs. Why not?
Answer 2: Is one of the conditions 'progressively finite' necessary for the other? and that the other is a sufficient condtion? Is it that the necessary condition and sufficient conditon are satisfied by finite graphs and only one of them is satisfied by infinite graphs?

Meaning of infinite path: What does an infinite path mean? When is a path infinite and when is it finite? Suppose we had just three vertices and a circuit along them, how many paths are there? Suppose we have an infinte number of vertices and the graph does not have loops and circuits. Does the graph have any infinite paths?? NO????? Are we getting confused between an infinite path [meaning a path of infinite length] and infinite number of paths?

Infinite sets: Here are two defs of infinite sets. 1 , 2.

A circuit induces an infinte number of paths on each of the vertices participating in it. Each of the infinite paths is of finite length. An infinte graph (for example the 1-d graph) has infinite number of paths, each of finite length. THEN WHAT IS AN INFINITE PATH? A path whose length is neither bounded by any integer nor there exists a finite number which can specity its length. What is such an example?

Theorem 2: If a graph is progressively finite and Gamma-finite, we have Gamma-hat(x) < inf for all x in X.

The theorem is kind of disturbing. This is because, it states that even in a graph with infinite number of nodes, it gives a statement about the cardinality of the set Gamma^hat. It says that the cardinality is a number, which is possibly unbounded. However, it is a finite number. See the definition of Gamma^hat.

Proof of theorem 2: Suppose the graph is progressively finite and Gamma-finite and that we had a vertex such that Gamma-hat(x)=inf. As the graph is Gamma-finite, x should be adjacent to a vertex x1 such that Gamma-hat(x1)=inf. by similar reasoning, x1 must be adjacent to x2 such that Gamma-hat(x2)=inf. etc... The path [x,x1,x2...] is therefore of inf length. Which contradicts that the graph is progressively finite.

Proof for necessity of theorem 1's premise: The method followed is proof by contradiction. The technique is the following: The theorem statement is of the form: A => B => C. With A being 'graph is Gamma-finite', B being 'graph is progressively finite', C being 'for all x in X, |Gamma^hat(x)| < inf '. B=>C is equivalent to NOT(B) OR C. We assume its contradiction is true; i.e., B AND NOT(C) is true and get a contradiction with A. proof method is: B and NOT(C) means, 'the graph is progressively finite' and 'there exists a vertex x (in X) such that |Gamma^hat(x)| = inf'. To get: contradiction with 'Gamma-finiteness of any vertex of the graph'.

let v be the vertex such that |Gamma^hat(x)| = inf. Let k be the number of paths out of v [objective: k is infinite] The graph is progressively finite meaning 'there exist no paths of infinite length' => all paths out of v are of finite length => There exists a path of maximum length (this is because, in a set of numbers of which infinity is not a member, we can always select an maximum). Then k*length_of_the_max_length_path is the upper bound on the number of vertices reachable by v. By hypothesis, this number is infinite.

Corollary 1: A Gamma-finite which is progressively finite at a vertex x0 is also progressively bounded at x0.

[The real punch line to this benign looking proof is applying the absolutely harmless looking theorem 1 to the subgraph induced by Gamma-hat(x) which happens to be finite.]

Proof of Corollary 1: The subgraph determined by the set Gamma^hat(x) is finite! So, applying the theorem1 to this subgraph, the terms 'progressively finite', 'progressively bounded' and 'without circuits' are equivalent.

[note the equivalence of 'without circuits' and 'cardinality of Gamma^hat(x)' as implied by the statement of this theorem.]

Fillable Holes in the proof of Corollary 1: from G to G' and back again. How can we make a statement about the graph G' when all we are talking about is about the subgraph induced by Gamma^hat(x0). Also, when and how are theorem 2, theorem 1 used? At what particular locations? How is the result for G' extensikble to G? remember, we are talking about two graphs here, G and G'. Also about two theorems 1 and 2. The statement of corollary 1, from the outside is more general, but needs to be taken care of.

Proof by contradiction: If Read the rest of this entry >>

Index Set Splitting of PUREs

(We use the notation of Saouter-Quinton-1203)
PURE: a Parametrized Uniform Recurrence Equation.
Index set splitting is a transformation that finds out if splitting a system of equations into individual sub-components can result in a set of SUREs. The scheduling of which can result in a better schedule.

What can be done better for PUNREs (Parametrized Unitarized Recurrence Equations).

Simple example for index set splitting:
Let the domain be 1 <= i,j <= N (the positive quadrant)

i <= j, X[i,j] = f(X[i,j-1])
i > j, X[I,J] = f(X[i-1,j])

The system can be broken down into two sub-domains
i <= j and i > j. Each of the subdomains have 1-d schedules. Read the rest of this entry >>

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 >>