Unbounded polyhedral domains and computability of SUREs

Problem: Give a single theorem that characterizes the theorems 1, corollaries 1/2 and skewed variations of corollaries 1/2. In other words, give a characterization of the computability of an SURE defined over an arbitrary polyhedral unbounded domain.

Explanation: The domain could be

F_n (as in theorem 1),

strip of the type Q_t* F_(n-t) (as in corollary 1/2)

a skew of the domain of collorary 1/2

a conical subset of F_n through the origin

a minkowski sum of a polytope and a cone (meaning, an arbitrary polyhedron which is a subset of F_n)


The statement of computability may be the following:

An SURE defined over an arbitrary unbounded polyhedral domain is incomputable iff

it has a cycle C of weight W(C)

-W(C) belongs to the characteristic cone of the domain.

Some assumptions

The SURE is defined as ... V_j(z-w_j)

The SURE is defined in all the integral (or rational points) in the domain

The RDG is strongly connected. We can do a greedy index splitting (ala Allan-Kennedy???)


We have two cones

C1: The dependence cone: constructed with the negative dependence vectors

C2: The characteristic (or recesssion) cone of the domain. This should have a vector other than {0} as the domain is assumed to be unbounded.

The convex cone of the (negative) dependence vectors strictly contains all the vectors which are the weight of cycles. Also, containing vectors just means of the same direction It could contain vectors which cannot be expressed by cycles of the weight vectors.

What has the separability of these two cones have to do with computability?: If C1 and C2 are separable, then of course the SURE is computable.

A sufficient condition for computability: If there exists a cycle whose weight is a vector that belongs to the two cones, then the SURE is incomputable. The weight vector of a cycle ofcourse belongs to a cycle. Does it belong to the char.cone of the domain?

How does the computability condition of SURE change if the domains are non-polyhedral, but still convex?
The concept of char.cone is from polyhedral domains. According to the book and lecture notes of Bertsekas et.al, the concept is perfectly valid in every convex domains. There are some caveats though. ????

Notes about importance of computability problem of S*RE's defined on unbounded Vs. bounded domains. According to QS, Unbounded domains are not that important while bounded domain are. This is because, they are more common. I disagree with this. More importantly, however, QS make the important observation that the computability problem of bounded domains is equivalent to the testing of the acyclicity of the EDG. From the outside, this seems like a condition which can be applied only to a non-parametrtized domain. However, thinking of the parameters as additional dimensions is a standard trick.
So, the question is given a bounded domain, and a computation defined over it, what is the computability problem?

Problem: An SURE defined over a bounded domain is computable iff, there exists no zero weight cycle.

Restatement of the problem: Given a partially integral polytope -- meaning some vertices are integral, others are rational -- find whether the polytope contains the vertex {0}

Algorithm:Use KMW decomposition. Find which edges donot participate in any cycle, remove them, recurse on the rest of the graph.


Question on finitizabilty of the domains

Later note:
I had originally defined the finitizability so the the computability condition of COR.1/2 of KMW can be applied to the case of SUREs defined over the skewed domains of COR.1/2.
Later note: With the precison we have for the condition for computability, we donot need this "finitizability".

Question: Given a computation defined over an unbounded polyhedral domain.
To find: A skew of the domain such that the application of which results in the maximization of for loops.

The number of finizable dimensions

the skewing matrix which can do this

A listing of the dimensions which are finitizable


Example1: if given a computation defined over Q_t * F_(n-t) (ala domain of cor.1/2 of KMW), we should give

a value of 2, meaning 1 out of the 2 domains is "finitizable"

The identity matrix: I_(2*2)

a listing of the domains which are finitizable: meaning j

Example2: If the domain of the computation is a skew of the domain of COR.1/2 of KMW, thr output should be

a value of 1, meaning 1 out of 2 domains are finitizable

a proper skew

a listing of the domains