Thursday, July 21, 2005

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