Qual Practice - Fall 2009 Part I (first two problems)

I am preparing for the qual now so I am going to write my answers to the previous qual questions here. That way my professors can see and critique my answers.

-----

Fall 2009 Part 1 - Problem 1:

CLAIM: The given problem can be reduced in polynomial time to the problem that is the same except that the paths are not required to have disjoint edges (only the nonterminal vertices are required to be disjoint.)

PROOF: Suppose we modify a given instance of the problem by stating that for each edge (A,B), we add a new non-terminal vertex C and replace the edge (A,B) with edges (A,C) and (C,B). Then for any path, each edge the path used in the original graph will correspond to a vertex that the path will use in the new graph. So then the condition of vertex disjointness will include the condition of edge disjointness.

(???)

----

Fall 2009 Part 1 - Problem 2

CLAIM 0: Given any collection of numbers A_i which can collectively be represented by X bits, their sum can be represented by at most X bits.

PROOF 0: Proof by induction on n, the number of numbers in the collection.
Base Case (n=1): Trivial, since the sum is just the number itself.
Inductive Case (from n=k, prove true for n=k+1): Let Y be the number of bits needed to represent A_1 through A_k. Then their sum also can be represented with Y bits.
If A_k+1 requires less than or equal to Y bits to represent, then it is at most 2^Y - 1, and since the sum of the others is also at most 2^Y - 1, the total sum is at most 2^(Y+1)-1 and can be represented in at most Y+1 bits. Since A_k+1 requires at least one bit to represent, X>=Y+1 and the statement holds
Suppose A_k+1 requires more than Y bits to represent. We know it requires X-Y bits. Then we have the sum of the others is also at most 2^(X-Y) - 1 (since that is greater than the bound of 2^Y-1) so the total sum is at most 2^(X-Y+1)-1 and can be represented in (X-Y+1) bits. Since Y must be at least 1, (X-Y+1) <=X and the statement holds.

CLAIM 1: If A can be represented by m bits and B can be represented by n bits, then AB can be represented by at most (m+n) bits.

PROOF 1: We must have abs(A) <= (2^m)-1, and abs(B) <= (2^n)-1, so we have abs(AB) = abs(A)*abs(B) <= (2^m)-1 * (2^n) -1 <= (2^(m+n))-1.

CLAIM 1.5: Given any collection of numbers A_1 through A_n which can collectively be represented by X bits, their product can be represented by at most X bits.

PROOF 1.5 (by induction on n)
Base Case(n=1): This is trivial, since the product of a single number is just the number itself.
Inductive Case (from n=k to n=k+1): Suppose that A_k+1 can be represented in Y bits. Then A_1 through A_k can collectively be represented in X-Y. So the product of A_1 through A_k can be represented in X-Y bits by the inductive hypothesis, and by Claim 1 the product of A_1 through A_k+1 can be represented in (X-Y)+Y = X bits.

CLAIM 2: An n*n matrix that can be represented in U bits has a determinant that can also be represented in U bits.

PROOF 2: Proof by induction on n.
Base Case (n=1): This is trivial, since the determinant of a 1x1 matrix is simply that matrix's single entry.
Inductive Case (from n=k, prove true for n=k+1): Consider a (k+1)x(k+1) matrix M. Let A be the number of bits required to express the entries in the first row; then U-A is the number of bits required to express the entries in the remainder of the matrix. Now consider the expansion of the determinant by minors using the first row of the matrix. We have:

(note: M(1,i) means the given entry of M, M{1,i} means the minor)

abs(det(M))
= abs(sum(i goes from 1 to k+1) of M(1,i) * (det(M{1,i}))
<= sum(i goes from 1 to k+1) of abs(M(1,i) * det(M{1,i}))
<= sum(i goes from 1 to k+1) of abs(M(1,i) * (2^(U-A)-1)) by the inductive hypothesis, since M{1,i} can be represented in at most U-A bits
= (2^(U-A)-1) * sum(i goes from 1 to k+1) of abs(M(1,i))
<= (2^(U-A)-1) * (2^A)-1 (by Claim 0, since all the M(1,i) can be represented in a total of A bits)
<= (2^U) - 1

So det(M) can be represented in U bits.

Since U is a polynomial in U, Part A of the problem holds.

For Part B, suppose that D is the total number of bits needed to store the denominators of the rational numbers, and thus U-D is the number of bits needed to store the numerators. Let k be the product of all the denominators. We know that k can be represented in at most D bits by Claim 1.5. Consider the matrix kM. We know kM is an integer matrix since we multiplied each value by a number that it is a multiple of its denominator. Also, the number of bits needed to store kM is at most (U-D)+((n^2)D) <= (U-D)+(UD) <= U^2. Thus by Part A the number of bits needed to store det(kM) is at most U^2. We know det(M) = det(kM)/(k^n), so the determinant of M can be stored with at most U^2 bits for the numerator plus no more than nD <= UD <= U^2 additional bits for the denominator, so the total number of bits is at most 2U^2, which is a polynomial in U.

For Part C:

Given an instance P = (A,c,b,K), consider the instance Q = (dA, dc, db, dK), where d is equal to the denominator of K, times all the denominators of the elements of A, times all the denominators of the elements of c, times all the denominators of the elements of b.

CLAIM 3: The instance Q can be represented in a number of bits polynomial in the number of bits required to represent P.

PROOF 3: Suppose P can be represented in A bits. Then since d is equal to the product of all the denominators, and since the denominators can be represented in less than or equal to A bits collectively, d can be represented in less than or equal to A bits. When you multiply each of the numbers d, you are adding at most A bits to the binary representation of each number, and there are (n^2+n+n+1) <= (4n^2) numbers. So the number of bits you end up with is at most A+(4n^2)A <= (5n^2)A <= (5A^2)A = 5A^3, which is polynomial in A.

CLAIM 4: All the numbers in Q are integers.

PROOF 4: Each number in Q is a rational number in P, multiplied by d, which is a multiple of its denominator.

(???)

--------

Fall 2009 Part 1 - Problem 3

Part A:

Proof by induction on n.

Base Case (n=1)

A new formulation

I have come up with a new formulation of the theorem in the last post that allows us to weaken the conditions necessary (and also make the proof a bit simpler). I also cleaned up the definitions a bit. Here is the new proof.

DEFINITIONS:

A "mark set" M is defined by a function M(f) that maps faces to edges in those faces. The domain of M, denoted by d(M), is a subset of the faces in the mesh.

A face f is "set by M" if f is in d(M).

An edge e is "marked by M" if there exists a face f such that M(f)=e. (In other words, e is in the range of M.)

M is "complete" if d(M) includes all the faces in the mesh.

Two mark sets M and N are "complementary" if the union of d(M) and d(N) is all the cells in the mesh, and the intersection of d(M) and d(N) is null.

The sum M+N of two mark sets whose domains are disjoint is defined so that:

(M+N)(f) = M(f), if f is in d(M),
(M+N)(f) = N(f), if f is in d(N),
and (M+N)(f) is undefined, if f is in neither d(M) nor d(N).

M is "consistent for C" (where C is a cell) if there exists an edge e in C such that M(f)=M(g)=e, where f and g are the two faces in C that contain e.

M is "valid" if for each cell C such that all four of the faces of that cell are set by M, M is consistent for C.

CLAIM:

Consider a mesh with two complementary mark sets defined on that mesh: M and K.

If the following condition is true:

(1) For each cell C, at most two of its edges are marked by K.

Then is is possible to find a set N whose domain is identical to that of M such that:

(2A) N+K is a valid mark set. (It is also complete by construction.)
(2B) For any face x that does not contain at least one edge marked by K, we have N(x)=M(x).

PROOF:

Consider the mark set N defined (over the same domain as M) as follows:

(3A) If the face f does not contain any edges that are marked by K, then N(f) := M(f).
(3B) If the face f does contain an edge that is marked by K, then N(f) := x, where x is one of those edges. (If there are more than one of those edges, we can choose arbitrarily.)

The following lemma is easy to see is true by construction:

(L) If the face f (where f is any face in the mesh) contains an edge that is marked by K, then (N+K)(f) equals one of those edges.

Also, by construction, N satisfies (2B) above. We must now show that N+K is valid.

Consider any cell C in the mesh. There are several possibilities:

(4A) C contains zero edges that are marked by K. Then all of C's faces are set by M, and (3A) is applied for all of C's faces, so the markings of C's faces in (N+K) are the same as the markings of C('s faces in M, which we know is consistent by validity of M.

(4B) C contains exactly one edge that is marked by K; call it e. Then by L, we have (N+K)(f)=(N+K)(g)=e, where f and g are the two faces in C that contain e. Thus we know N+K is consistent for C.

(4C) C contains exactly two edges that are marked by K. If these edges do not share a vertex, they thus are not both contained in the same face, and the argument in (4B) applies to each of the edges. If the edges do share a vertex, that means that both of the edges are contained in one face, and each edge is also contained in another face that it doesn't share with the other edge. Suppose that the two edges are e and f, and e is contained in faces x and y, and f is contained in faces x and z. By (L) we have (N+K)(y) = e, and (N+K)(z) = f. We have that (N+K)(x) can equal either e or f, and we don't know which, but whichever one it equals it will still satisfy the consistency condition.

----

The way we use this proceeds as before - put all the faces that got merged in K, and put the existing markings for the rest of the faces in M.

A performance result

DEFINITION:

We will use "edges", "faces", and "cells" to mean 1-cells, 2-cells, and 3-cells respectively. (This terminology is appropriate here because of the unique role played by each dimension of cell in this problem.)

A set of marks M is defined by a function M(x) that maps faces to the edges that are marked in them. If a face is shared by two cells, it is considered just one face.

An edge e is "marked by M" if there exists at least one cell x such that M(x)=e.

CLAIM:

Suppose we have a mesh that is validly marked - call this set of marks M. Then suppose we take a subset L of the faces in that mesh, which we will call the "locked" faces. Define a function K(x) that maps each face in L to one of its edges. (Effectively, L and K(x) define a partial set of marks. This set does not need to coincide with M in any way. We define "marked by K" in the same manner that we defined "marked by M" above.)

Also, note that M doesn't have to be a complete set of marks; we don't have to specify values of M(f) for faces f that are in L (and M only has to satisfy the condition that each cell has an edge that is marked twice for those cells that have values of M(f) for all four faces; see below).

If the following conditions are true:

(1A) On each cell, at most one face is locked.
(1B) Any non-locked face shares an edge with at most one locked cell.

Then there exists a valid set of markings N of the mesh such that:

(2A) For any face x in L, N(x) = K(x).
(2B) For any face x that does not contain at least one edge that is marked by K, N(x) = M(x).

PROOF:

Consider the function N(x) defined as follows:

(3A) If x is in L, then N(x) = K(x).
(3B) If x is not in L but it contains an edge marked by K, then N(x) equals that edge. (Note that by condition 1B, it is impossible for x to contain two edges each marked by K.)
(3C) Otherwise, N(x) = M(x).

By construction, this function satisfies conditions 2A and 2B above. We now must show that this set of markings is valid.

Consider any cell C. There are several possibilities:

(4A) Suppose none of the edges in C are marked by K. Then (3C) is used for all faces in C, so the set of markings for that cell in N is the same as that in M, and we know M is valid for C by hypothesis.

(4B) Suppose there exists an edge e in C that is marked by K, but no cells in C are in L. Then there will be two faces in C, call them f and g, that contain e. By (3B), we have N(f)=N(g)=e, so C is validly marked since two of its faces share a marked edge.

(4C) Suppose there exists a face f in C that is in L. Let e=K(f). By (2A), we know that e=N(f). Also, C has another face g that also contains e. By (1A), g is not locked, so by (3B) we have e=N(g), which means f and g share a marked edge and thus the cell is validly marked.

-----

So, what does all this mean for our original problem? Well, let's say we have our original mesh, and then we contract an edge. Put all the faces that got "merged" by that edge contraction in L, and for the rest, keep the original markings and call it M. Now whatever we set the markings in L to, we can guarantee that we won't have to change the markings on any cell that isn't adjacent to one of the edges we just marked in L. This means that we have an effective upper bound on how many cells we will have to change, and also means that we have a simpler optimization problem since we just have to look at how to mark the cells in L, and let the algorithm above do the rest.

Of course this is contingent on the conditions 1A and 1B above being true, but those shouldn't be too hard to satisfy.

More on the graph method

So I thought a little more about how the graph method (number 3 in the list in the last post) works when you are doing edge contractions. In an edge contraction, each pair of faces on opposite sides of the contracted edge gets merged into one face. That means that if the two faces had different edges marked, then you have to switch one of them so it matches the other edge. This can be simulated in the graph method by having an extra node for each of these pairs that has out-degree 2, one going to each of one of the possible switches. The trickier thing is dealing with the fact that there are multiple of these forced switches at the same time. Suppose that on one of the cells we have to do a given marking switch due to the edge contraction, then we propagate it back until eventually we hit another marking switch that we had to make due to the same edge contraction. This means that we have made both of those changes at one time.

When you put it all together this gives an algorithm for the problem:

1. When you create the mesh and initial markings, also create the graph. You also have to update the graph each time you refine, coarsen, or change the markings - but this only affects the cells where the markings were changed so it takes (on average) constant time.

2. When you contract an edge, make a list of all the pairs of opposing faces that don't have edge markings that correspond.

3. While that list still has elements in it:
3a. Do the search process starting from one of the elements in the list (chosen arbitrarily), searching for either (a) one of the other elements in the list or (b) a node with out-degree 0.
3b. Make the edge switches called for by the result of the search, updating the graph as necessary.
3c. Remove the chosen element form the list. Also if the search process ended at one of the other elements in the list, remove that element as well.

This by itself is probably not the best algorithm we can come up with because it is likely to change the same cells over and over, and also looks that each required change one by one rather than considering them all at the same time. But it is a simple algorithm that provides a baseline that we can use as a point of comparison to evaluate more sophisticated options. Probably the next thing I will do is implement this algorithm (not necessarily in the TentPitcher codebase, just a prototype implementation in Python or something) to see how well it works.