Student Post: Cleaning up Graphs and Code

This week was largely spent on cleaning up my code for the Petersen graph and the graph of K6 (also I changed how K6 looks as a 3-D model completely). Since I am very new to OpenSCAD, my code was very length and a lot of it was unnecessary. I saved well over 40 lines in total between the two graph codes. Over spring break I hope to work on the other members of the Petersen family of graphs, now that I know how to speed up the process with for loops in OpenSCAD.

New K6 Graph and Code

In last week’s post, the gif of K6 was all over the place. There wasn’t much symmetry to the graph in my model of it. Dr. Taalman suggested I position the points around a circle, rather than just winging the coordinates. this resulted in a much better representation of K6 (see gif below).

And here is the (much shorter) code that made the new representation of K6 For the Petersen graph, I tidied up the code in the same fashion. The actual representation of it looks the same overall, just a bit bigger now that my code has a parameter section and due to the fact we are looking to print out these models.

Until next time,

Hannah Critchfield

Student Post: Streamlining the Tools

This week I was tasked with trying to ‘highlight’ a circle if selected. Currently, I am struggling with how to calculate the intersection if a user selects an edge because a disk has three incoming edges in which the other endpoint is a point and thus was not able to complete this task. However, I was able to streamline some of the code for the tools that are currently available. Last week I added buttons to the screen which allowed the user to click on which tool they wanted as opposed to using the keyboard. However, in order to draw a circle the letter ‘C’ still needed to be clicked. One issue that I encountered with still using the key for the circle tool was that it changed the point editing tool to the circle tool indefinitely which resulted in no longer being able to drag points. Now the circle tool is a subclass of the point editing tool. The two different buttons for point and circle switch between the tool and thus we have returned to our functionality below I have included a picture of what the current tool bar looks like.  Next week, I will have it so when I user selects a circle it will change colors and also that when the user selects a point those will change a color before an object is drawn with them. Until then,

Student Post: The Beginning of the Petersen Family of Graphs’ Journey into Space … 3-Space

Graphs can be a funny thing. When you say “graph”, some people will thing of a line or some other function in 2-D. Other people will think of marvelous planes and surfaces in 3-D. Fewer people will think of “standard” graph theory type graphs represented in 2-D. And even fewer people will think of those graph theory type graphs represented in 3-D. My goal is to change that.

Throughout the semester, I want to highlight the Y-Δ and Δ-Y transforms that allow you to go between graphs within the Petersen family of graphs. The names Y-Δ and Δ-Y are quite visual. In Y-Δ you are replacing 4 vertices that make a Y shape with 3 that make a triangle shape and in Δ-Y you are replacing 3 vertices that make a triangle shape with 4 that make a Y shape. Now, when the Petersen family of graphs are represented in 2-D, these Y-Δ and Δ-Y transforms are not quite apparent. I am hoping that representing these graphs in 3-D will make these transforms a bit clearer.

Since this is my first exposure to OpenSCAD (and really my first exposure to modeling something in 3-D all my own), I’m going to start off the semester by getting the Petersen family of graphs in 3-space and then go from there. This week we have the famous Petersen graph and Kbeing featured.

The Petersen Graph

Bringing the Petersen graph into 3 dimensions was quite exciting. The Petersen graph is classically portrayed as a big pentagon with a small star in the middle, like this: As you might be able to guess, the Petersen graph is nonplanar. We can’t draw it on a plane without its edges overlapping. However, if we allow ourselves an extra dimension, we can represent the Petersen graph without any edges overlapping.  Just like in 2-D, there are different ways to represent the Petersen graph in 3-D. Above is the one I chose to start my OpenSCAD intro with. I created it using an edge code my mentor, Dr. Taalman, sent me. Here’s a picture of my code! K6

Now, even though Kdoesn’t look as complicated as the Petersen graph (it only has 6 vertices!), it is much more complicated to graph in 3-D while avoiding edges crossing over. The view from the top down doesn’t look like K,but when you move ever so slightly, you can see edges that weren’t visible before.

With the Petersen graph, I only had to adjust the height of a few points. However, Kis a completely different beast in that regard. Here is a spin around the graph! As you’ll be able to see, Kin 3-D (or at least how I’ve represented it, there are probably cleaner ways) gets pretty intricate compared to the Petersen graph above! Hopefully next time I will have the other 5 graphs from the Petersen family to show you all, since I am much more familiar with OpenSCAD. I can tell that showing of the Y-Δ and Δ-Y transforms will be a challenge — but I’m excited!

Until next time,

Hannah Critchfield

Student Post: Simple Introduction To Rigidity Figure 1. Convex v. Non-Convex

The figure on the left is a convex polyhedron, while the figure on the right is non-convex. What makes the cube on the left convex is that any two points can be connected by a line segment within the interior of the polyhedron. Looking at the figure on the right, we can see that two points can be connected on its exterior making the polyhedron non-convex.

Let’s quickly define polyhedron. A polyhedron is a three-dimensional figure made up of flat polygonal faces joined by straight edges. Polyhedra can be classified by the number of faces they have. For instance, a 4-sided polyhedron is called a tetrahedron, 5-sided is a pentahedron, 8-sided is an octahedron, and so on.

What makes a polyhedron rigid, you ask?

A polyhedron is rigid if you cannot bend it into another configuration and it remain the same shape. Bending a polyhedron into a congruent configuration would mean that as you move the figure the faces do not change and the edges preserve their length. With rigid polyhedra, however, trying to bend it would result in a tear or break. Take a cube, for example. Figure 2. A Rigid Polyhedron (Cube)

If you had this cube in your hands, then you could easily find that bending or deforming it could not be done.

This brings us to the Cauchy Rigidity Theorem (1813), in which Cauchy states that any convex polyhedron is rigid. No convex polyhedron can be bent or deformed.

So, what about non-convex polyhedra? It turns out that there exists non-convex polyhedra that can in fact be bent into another configuration and remain the same shape. This is called flexibility. You have a polyhedron (which must be non-convex), you bend it, and you have a polyhedron that is congruent to the one you started with but arranged in a different way. A simple definition of flexibility is continuously moveable. A flexible polyhedron can be moved in a continuous motion.

Raoul Bricard, a French mathematician, constructed the first flexible polyhedron that had self-intersections in 1897. A self-intersection means that two or more edges cross each other. This construction is called the Bricard octahedron and consists of six vertices, twelve edges, and eight triangular faces (hence the name). Figure 3. Bricard’s Flexible Octahedron With Self-Intersections

Fast forward about 8 decades later when in 1977 an American mathematician by the name of Robert Connelly constructs the first flexible polyhedron that did not have self-intersections. Connelly actually disproved Leonhard Euler, who argued in what is known as the Rigidity Conjecture (1766) that all polyhedra are rigid.

The best and simplest construction of a flexible polyhedron was built by German mathematician, Klaus Steffen. This construction consists of 9 vertices, 21 edges, and 14 triangular faces. Figure 4. Steffen’s Flexible Polyhedron Without Self-Intersections

I have made Steffen’s polyhedron and you can as well! Follow this template along with the following instructions so that you may physically feel the flexibility. This model is meant to be made out of paper. Note that even if you made Steffan’s flexible polyhedron out of metal plates with the edges as hinges that it would remain flexible.

Now that we have covered rigid and flexible polyhedra, we can discuss the bellows conjecture. Does the volume inside of a flexible polyhedron vary while we bend it? Ijad Sabitov proved in 1995 that there does not exist a construction of a flexible polyhedron that has variable volume as you move it. A flexible polyhedron has the same volume regardless of its state of flex. In other words, a flexible polyhedron would make a terrible bellow.

I have been told that “the bellows conjecture” is quite a misleading name.

Written By: Brittany Braswell

References:

Figure 1. liam.flookes.com/cs/geo/

Figure 2. By Tomruen at en.wikipedia [Public domain], via Wikimedia Commons

Figure 3. en.wikipedia.org/wiki/Bricard_octahedron

Figure 4. By Unknown at en.wikipedia [Public domain], via Wikimedia Commons

The Discrete Fourier Transform

The Fourier Transformation is a high level mathematical function using the integrals over a continuous wave to compute the component that make up such a wave. As this is done in a continuous fashion, the Discrete Fourier Transform(DFT) is not. The DFT uses the summation of real numbers representing points in time of wave motion. Which makes it an extremely powerful tool to computers because of their discrete nature.

This transformation is accomplished by computing the value of each signal component using every point in time chosen. Every signal value is made of a summation of all the points in time chosen with the value of the signal applied. This is done in the form of circle rotation. Euler’s formula allows us to recognize a basis of imaginary polar coordinates where $e^{ix} = cos(x) + sin(x)i$, thus creating an arbitrary point in $R^2$. This basis allows us to apply an exponential rotation to all of our points $x_n$, where K is the signal component being evaluated and n is the point in time. After the transformation is complete we are left with a “list” containing all of the signal components of the original wave.

Written as: $X_k = \LARGE {\sum_{n=0}^{N-1} x_n e^{-i2 \pi k \frac{n}{N}}}$

When the DFT is implemented on an algorithmic level it becomes quickly apparent that this runs at an $N^2$ time complexity belonging to $O(n^2)$. That is because to compute every value we must add together all of the point by point computations. Also, because of the discrete computation this algorithm is implemented using arrays. Where every index in array K is filled with the summation of points stored in array n. Finally, array K contains the value of every signal component spanned by the wave points chosen. While $O(n^2)$ isn’t inapplicable, the Fast Fourier Transform creates a one layer speed up in time complexity to reach $O(n \log n)$.

The Fast Fourier Transform

The Fast Fourier Transform, or FFT, is a proven way to implement a substantial array transformation on a large amount of data, due to its time complexity of $O(n \log n)$. This speed up was possible due to the amount of redundant calculations made by the Discrete Fourier Transform. These redundant calculations come from the periodic nature of imaginary numbers, where $i^t = -i^{4t}$. Due to this property, by splitting the data up into even and odd indices, we are then able to apply the logarithmic time complexity. Using our original equation $X_k = \LARGE {\sum_{n=0}^{N-1} x_n e^{-i2 \pi k \frac{n}{N}}}$,

and denoting $e^{-i2 \pi k \frac{n}{N}}$ as $W^{nk}_{N}$. So we have $X_k = \LARGE {\sum_{n=0}^{N-1} x_n W^{nk}_{N}}$,

Now that we’ve condensed the formula, it becomes possible to split between indices $2m$ and $2m+1$, as halves of the array n respectively, to perform the Fourier transform as: $X_k = \LARGE {\sum_{m=0}^{\frac{N}{2}-1} x_{2m} W^{2mk}_{N}} + \LARGE {\sum_{m=0}^{\frac{N}{2}-1} x_{2m+1} W^{(2m+1)k}_{N}}$

Now that the formula has been established and we are aware of the properties of W as $W^{4k}_{8} = -W^{0k}_{8}$ $W^{5k}_{8} = -W^{1k}_{8}$ $W^{6k}_{8} = -W^{2k}_{8}$ $W^{mk}_{8} = -W^{(m-4)k}_{8}$

Where N is equal to 8.

We define the even summation of the FFT as $latex G[m]$ and the odd summation as $H[m]$. Therefore we can see that: $X_0 = G + W^{0k}_{8}H$ $X_1 = G + W^{1k}_{8}H$ $X_2 = G + W^{2k}_{8}H$ $X_4 = G + W^{4k}_{8}H = G - W^{0k}_{8}H$ $X_5 = G + W^{5k}_{8}H = G - W^{1k}_{8}H$

Given that the input is a power of 2, we can then perform the operation know as the decimating-in-time-algorithm. This is, recursively breaking down every set of transforms into even and odd inputs until only two point DFT’s remain. That is, $\frac{N}{2}$ point transformations, where we implement the recursion $\frac{N}{2}...\frac{N}{N/2}$ until hitting summations or arrays of length 1. At each stage of the algorithm $\frac{N}{2}$ complex operations are needed to build the previous level. Because of the stage construction in \log N, we only have to compute the summations of values themselves N,  while recycling the complex computations.

Quantum Fourier Transform

Now that this basis has been firmly established and we have denoted the fastest time complexity of the Fourier transform using classical computing as $O(n \log n)$, we can further use Quantum gate transformations to a achieve a time complexity such as $O(\log n)$ . Needless to say, this is an exponential speed up of an entire magnitude. To define the transform we first note that $X_k$ can also be defined as set of column matrices denoted as $X^{(s)}$, where s the index of the “array”. We then form the formula as $X^{(s)}_{j} = \LARGE {\sum_{n=0}^{N-1} P^{(s)}_{jk} X^{(s+1)}_{k}}$

While this may seem complex, it is important to realize this is a re-representation of the previously defined FFT formula in order to define $P^{(s)}$ as a form of column matrices. As we know from the previous post, qubits are defined as column vectors representing system  state probability. If we can reform our input array to be represented as such then we can apply our gate matrices in order to introduce a state of superposition.

Following this the form of basis P is proven under a few propositions, however for the sake of this article we will assume the propositions as true while giving a brief explanation for each.

1.   Each row of matrices $P^{(s)}$  only contains two non zero entries

In the matrices of $P^{(s)}$  we see that the non zero entries are located in the main diagonal and the sub-diagonal depending on the column values of $j$. If we look at this a little closer it becomes clear why this. Putting at this in terms of a double array, if indices $i$ and j are equal at all times then we will receive only the diagonal values stored in the array and the same for our matrices. When $i = j$ we traverse all indices in the main diagonal of each matrix, when $i = j - 2$ we receive all entries in the lower sub-diagonal, and $i = j + 2$ yields all entries in the upper sub-diagonal. Because we assumed proposition one we can now say each matrix has been defined depending on the piece-wise function of the indices i and j.

2.  The matrices of are unitary

If you refer from the last post, unitary is defined as a square matrix where the conjugate transpose is also its inverse. Recall, we need this to be true in order to evaluate output transformations as we due input, in our time steps denoted by t. Subsequently, this allows these quantum gates to be implemented on a quantum computer. However, we must determine what these gates are first. We do this by whats called QR decomposition. The decomposition states that any matrix belonging to $P^{(s)}$  can be broken up into the product of a unitary matrix $M^{(s)}$  and an upper triangular matrix $N^{(s)}$ This then brings us to our next proposition.

3. For any matrix s belonging to $P^{(s)}, s$   can be made up of the matrices $M^{(s)}$ and $N^{(s)}$

Because the depth of the proofs are being conceded right now, I am going to use proposition three in order to explain the mathematical composition of both $M^{(s)}$ and $N^{(s)}$ . Firstly, by multiplying the matrices M and N before traversing the matrix on the left side of the solution we can see that these sets of matrices build $P^{(s)}$ , such as $\LARGE {(M^{(s)} N^{(s)})_{jk} = M^{(s)}_{jk} N^ {(s)}_{kk}} =P^{(s)}_{jj}$

We then denote that matrix $M^{(s)}$ can be written as its form of induction using the Identity $I$ and the Hadamard matrix H. By recursively using the formula $\LARGE {M^{(0)}_{2n \times 2n} = I^{\otimes (n-1)} \otimes H}$

for every matrix of matrices $M^{(s)}$ we can see this induction compose to $\LARGE {M^{(s)}_{2n \times 2n} = M^{(s-1)}_{2n-1 \times 2n-1} \otimes I \otimes H}$

Thus, building every matrix belonging to $M^{(s)}$ and completing the unitary requirement of $P^{(s)}$

Lastly, we form our matrices of N as triangular matrices. This is simply the product of all triangular matrices in reverse using R at time $u = t - s + 1$ denoted by $N^{(s)} = \LARGE {\prod_{t=s+1}^{n-1} P^{(s,t,u)}}$

Finally, we are able to build the Quantum Fourier Transform from the defined decomposition. We first prepare our quantum state as $\left|\varphi \right>$ and every complex matrix in $P^{(s)}$ such as, $\left|\varphi_0 \right> = P^0, P^1......P^{(n-1)} \left|\varphi_n \right>$

Where $\left|\varphi_n \right>$ contains every value of the input $X^{(n)}$ in the form of ket complex matrices.

Thus we can say, $\left|\varphi_0 \right> = \sum_{c_{n-1} ... c_{0} < 1} X^0_{c_0... c_n-1} \left|c_{n-1} ... c_0 \right>$

The algorithm takes a complex array X as input and uses our quantum gates in $P^{(s)}$ to output a quantum state that correspond the probabilities of the real values and amplitudes, given by the original DFT. Thus, we prepare our quantum register of input as $\left|\varphi_n \right> = \sum_{k = 0}^{N-1} X_k \left |k \right >$

We then move in reverse as an outer loop from $s = n -1 \rightarrow 0$

and as an inner loop from $t = n -1 \rightarrow s + 1$ .

At every step in t, we apply our unitary gate operation of $N^{(s)}$ as $R^{(s,t, t -s +1)}$

After applying the quantum gate operation to every matrix at step t, we apply the Hadamard matrix to the value of $X^{(n)}$ at time step s.

After completing every matrix in the reverse time step of s, we have completed the algorithm, this yielding a quantum state $latex \left|\varphi_n \right>$ corresponding to elements of the complex matrix Y.

If we evaluate the time complexity of this transformation we see that the outer loop as $n(n+1)/2$ steps or equivalently $O(n^2)$. We see that classically this is equal to the original DTF, however every qubit operation compounds the probabilistic superposition to $2^n bits$. Due to this we can say that the operation becomes $O(log n)$. This incredible exponential speed up becomes the driving factor of the algorithm and the reason it must be defined in terms of qubits and quantum space.

Written By: Mitchell Mesecher

Student Post: Adding Buttons!

This week and the previous week I was tasked with adding buttons to our user interface. Currently when the buttons A, P, or C were clicked it selected a certain “tool” that you could use. This week I was attempting to create buttons so that instead of having to click a keyboard key the user could click a button. I was able to create buttons, however, I unintentionally over wrote the frame for the Python Interpreter so the buttons are on the wrong screen. I believe that this will be a quick fix and that all I need to do is create a new content pane and add that to the frame with the arcball because currently it is adding buttons to the content pane of the python interpreter. A picture of the issue is included below. The reason we are making this change is because as we add more features the use of keyboard keys would become too extensive. That is all for this week. Until next week,

Student Post: The Rabbit Hole of Graph Theory Terminology (Plus some Petersen Graphs)

My first ever exposure to any sort of graph theory was through this paper by Flapan, Mattman, Mellor, Naimi, and Nukkuni. If you’ve already clicked on the link, you might see how someone could get overwhelmed with terminology early on in the paper. Since I had no prior knowledge to graph theory, that person was me. The goal of this post is to provide some casual definitions and some examples showing off certain properties. (Note: this will not cover all definitions in the paper, and certainly not all definitions in graph theory, just some ones that I wish I knew before reading the paper/some ones I think need extra attention.)

[Note: all images are either from the paper linked above, or are from the wikipedia article linked in the definition title preceding the image.]

Definitions and Examples

Planar Graph: A graph is planar if it can be drawn on the plane without any of its edges crossing. (Note: only one way of drawing the graph without the edges crossing has to exist for it to be planar.)

KnThis is a complete graph with n vertices. It will also have n(n-1)/2 edges. Below is a picture showing off Kfor n=1…12 along with the number of edges the graph has.for Minor: Let G be a graph and H be a subgraph. A minor of a graph is created by deleting edges and vertices, and contracting zero or more edges. (Note: when you contract an edge, the two vertices at the end of that edge merge.) Below is a diagram of a G: graph, H: minor of G, and how the minor was formed. The dotted line represents the deletion of an edge, while the grey line represents the contraction of an edge.

Y-Δ Transform/Move: Let G be a graph that has a vertex, v, and let have exactly three other vertices surrounding it. A Y-Δ transform of G at v is achieved by removing v from G and adding edges between each pair of the neighboring vertices.

Δ-Y Transform/Move: Let H be a graph that has a triangle of vertices, uvw. A Δ-Y transform of H at uvw is achieved by removing the edges uvvw, and uw from H and adding a new vertex, z,  and new edges uzvz, and wz.

So, in Y-Δ transforms you are deleting a vertex and in Δ-Y transforms you are adding a vertex. These transforms will be useful for understanding an upcoming definition.

Petersen GraphThis is a graph with 10 vertices and 15 edges. Click on the link and scroll to read about some neat properties Petersen Graphs have. If I listed them all here, this definition would be the length of the blogpost.

Petersen Family of GraphsThis is a set of seven undirected graphs (graphs in which the edges don’t have direction) that includes the Petersen graph, the complete graph Kand 5 other graphs that are formed by Y-Δ and Δ-Y transforms. Below are two images: one from the paper mentioned at the beginning of this post and one from the Wikipedia page linked in this definition. Both show the Petersen family of graphs, but the Wikipedia picture shows which graphs can be formed by performing Y-Δ and Δ-Y transforms.  Upcoming

If you clicked on the paper mentioned at the beginning of the blog post, you may have noticed that the definitions featured here only cover the first three pages. These definitions and examples were chosen because they are going to be heavily used in what I want to do next. Past posts by Ben Flint have shown off Petersen graphs represented in 3-dimensions. My goal for the semester is to represent K6 , K3,3,1 , a Petersen graph, and the other 4 graphs in the Petersen family in 3-dimensions. A stretch goal/side project is to create some sort of program that will perform those Y-Δ and Δ-Y transforms on the Peterson family of graphs (and potentially others as well).

Until next time,

Hannah Critchfield