March 21, 2019 by williamrnettles
Student Post: Visualizing Bipartite and Complete Graphs in 3D Space
Bipartite Graphs
When thinking about how to represent bipartite graphs in 3D space, the challenge arose: how do we take full advantage of this extra dimension. The models we started with worked fine as they were, but we weren't fully satisfied. As seen below, our current model for the graph K44 appeared in space as two graphs of K22 stacked on top of one another and rotated 45 degrees. We knew we could do better.
Original graph for K44
What followed was a simple, yet elegant solution to the problem. For a graph KNM, the points N are plotted along the Z axis while the points M are plotted along a circle around the origin. What resulted can be seen below in our new graph for K33.
K33 using the Line and Circle model
3D printing the graph for K33 only solidifies the simplicity of the design; however, the true beauty of the design is how it can be adapted to a general solution for all values of KNM
The Line and Circle Model
K5-5 using the Line and Circle model
The line and circle model is perfect for relatively small values of KNM as it clearly displays the relationship every point has with each other. However, for increasingly larger graphs, It becomes clear that points plotted along the line are allocated significantly less space than those along the circle. As such the points may begin to appear unevenly distributed as the size increases. This can be useful, for displaying graphs KNM where N and M are different values, such as K6-10.
The Semicircle Model
After developing and printing graphs for the Line and Circle model, we had a desire to iterate upon its design. Our original idea involved plotting the points of K33 on the vertices of an octehedron, but the model itself soon generalized to plotting the points of the graph along opposing, perpendicular semicircles. As such is distributes the vertices of the graph evenly across the model. The semicircle model is more suitable for visualizing larger graphs, but can feel rather sparse for smaller values such as K33. Graphs of KNM where N and M are not even can also appear lopsided, as the nature of the semicircle model's visual symmetry relies upon the two plots being equal.
K55 Using the semicircle model
Streamlining the Code
After developing our two models for bipartite graphs, our next objective was to make it easier and less time consuming to create graphs in openSCAD. Up to this point, we had been manually plotting points in the code. While we already had code to connect lines between points, meaning most of the hard work was already done, for the work of plotting points for each (increasingly large) new graph we wanted to print was still very time consuming. It would be entirely impractical to plot something as large as K20-20 for instance without more advanced code.
K20-20 Using the semicircle model
I developed the code to the point where for any two values for KNM, the program would automatically create the corresponding graph in either model and scales it appropriately.
Below is the code for plotting a graph using the line and circle model. This was easily the most complicated part of the process, as it required splitting the points into 3 separate variables. The variable k plots all of the Line vertices while v and z each plot half of the circle vertices.
Because these two models for bipartite graphs could be generalized so easily, we were able to write code that could plot a graph of any size in seconds. Having reached a good stopping place for bipartite graphs, we began looking towards modeling complete graphs.
Complete Graphs
Immediately it became apparent that generalizing a model for complete graphs would be quite unfeasible, as applying any really symmetry to them would result in intersections. We still wished to generalize them in some way, and while the first model we arrived at did have some merits, it was not quite satisfactory. We called this model the Dome Projection of a complete graph.
Dome Projection
https://en.wikipedia.org/wiki/Book_embedding
The idea behind the Dome Projection model to plot the vertices of the graph on a circle, then connect them by projecting their edges on different 'dome levels'. The code for it works by starting from a single vertex and connecting it to every other point. It then increases the dome level, moves to the next vertex and connects it to every vertex it is not yet connected to, proceeding like this until ever vertex is connected to every other vertex.
Dome Projection for K5
One interesting thing about the Dome Projection is its relation to another way of representing graphs, the Book Embedding method.
A Book Embedding of K5
Book embedding works by connecting the vertices of a graph on different planes or 'sheets', connecting all possible points to each other without intersections then moving onto the next sheet and proceeding in this way until every vertex is connected. We quickly discovered that the number of sheets in a book embedding corresponded to the number of levels on a dome projection. As seen above, the dome projection for K5 has 3 levels while the book embedding has 3 sheets.
Dome projection serves as an interesting new way to represent graphs and certainly looks nicer on a desk than a book embedding, however it was still not quite what we were looking for from a 3D modeling of complete graphs.
A Better Representation
Even though its unlikely a generalized form for the complete graphs exist in 3D space, we sought to find something close, at leas for relatively small values of K. Starting with K6, The first model we constructed involved plotting pairs of points at different Z values and rotating them around the Z axis. What resulted appeared as a tetrahedron with two points inside of it. This tetrahedral visualization for K6 attempts to preserve as much symmetry as possible in the graph with hopes that doing so could provide a method to visualize large KN graphs, such as K8, with as much order as possible. This visualization does work well for K6 but does begin falling apart at K8. Though no graphs larger than K8 have been modeled in this way yet, it's safe to say this trend would continue.
Plotting K8 with the tetrahedral visualization
Our second visualization for K6 takes things in a different direction. Instead of generalizing a model for the graph, it aims to generalize an algorithm for determining the model for each individual graph. The code we used for it plots the points of the graph randomly on a sphere then calculates the distances between every edge for a given number of trials. The model that has the largest distances between edges is selected as the new best model for a given graph. It takes millions of trials to get a reasonable result, however, that result it striking .
Two Visualizations for K6
Order and Disorder in 3D Graphs
On the left is the graph for K6 we started with when this project began. It was created by stacking two graphs for K3 on top of each other and rotating them so that their edges don't intersect. On the right is the graph for K6 that our code produced. After a semester and a half, we ended up exactly where we started. There's some beauty in this, however, as somehow, a model created through order and a model created through chaos ended up appearing strikingly similar. This could just be coincidence, or it could be a result of the absurd poetry that is Math.
As we move forward in this project, we plan to continue finding new models for larger complete graphs. We're excited to see what these graphs end up looking like, as everything after K6 is new territory at this point.
March 21, 2019 by swareyle
Rocket Flame Trench 3D Printing Project
Last semester as well as this semester, I have been working with Dr. Taalman to produce a 3D printed model of the rocket flame trench that is located at the launchpad in NASA's Wallop Flight Facility on Eastern Shore Virginia. When a rocket is launched it generates a lot of heat, and the trench directs the exhaust and heat away from the rocket.
Dr. Lubert, who is currently researching how to minimize the vibration caused by the rocket launch noise, gave us several blueprints and pictures of the trench. This gave us an idea of the shape of the trench.
Our first step was to see if Fusion 360 had the tools we needed to design the model. We tested our idea on how to build the model in Fusion 360 and printed an object that has a similar shape as the trench.
After we had figured out that we could design the model in Fusion 360, we scanned the blueprints and up loaded them to the Fusion 360 cloud. Since the blueprints contain proprietary information, we also removed all the measurements from the blueprints in case Fusion 360 was hacked and the blueprints stolen. (The blueprints will be available at the presentation.)
Once the blueprints were in Fusion 360, we sketched the shape of the trench by tracing over the blueprints. Since we do not have blueprints for the cross sections of the trench and for the top, we will need to use available pictures to help us to determine the shape of these sections
At this point, the side section of trench has been sketched. The top and front sections still need to be sketched. Once the model has sketched and the different planes connected to a make a 3D model, the model will be ready to print. The printed model will give Dr Lubert a better understand of the shape of the trench and how a rocket's exhaust flow through and exits the trench.
Source: https://geekhaus.com/mathmakerlab/portfolio/214/
Photo Credits: Dr. Lubert and Lyndon Swarey
March 19, 2019 April 4, 2019 by abbyeget
Student Post: Rolling Trefoil Knots
Dr. Laura Taalman and Dr. Stephen Lucas have been researching rolling trefoil knots since before we (Abby Eget and Harley Meade) became involved with the project. When we joined the research team, we were fortunate enough to come into the project with a lot of previously coded information in OpenSCAD including the general shape of the Morton trefoil, which is tritangentless, which is what allows it to properly roll. Then we helped the team optimize the knot using a parameter a, in accordance to the formula in the section below, so that there was minimal variation in the height of the center of mass.
Optimizing the z value using the a value:
Originally the plan was to optimize the a value by scaling by 1 in the z direction. This was done surprisingly quickly, so we shifted directions. Instead of optimizing the a value for scaling by 1 in the z direction, we decided to try to optimize the scaling in the z direction based on varying a values. We used a values of 0.3, 0.5, 0.7, and 0.9.
Coded knot with a = .5
We printed the four trefoil knots with the four different a values from Shapeways. Then we printed four corresponding convex hulls in our own Maker Lab. These are pictured below.
a = .3 scaling = .4629
a = .7 scaling = 1.3162
Varying heights of the center of mass for knots of varying a values with z-scale 1.
Knot paths:
After considering how the knots rolled in relation to their convex hulls, we decided to use the triangles from the convex hulls' code to see what kind of paths the knots make when rolling on the table. Two of these are pictured below, with the black line showing the horizontal shift in center of mass.
Path of Morton trefoil knots with a = 0.3 and a = 0.5
Two other parameters that we changed are the p and q values of the knots. These are related to the fact that the trefoil is a torus knot, where the p represents how many times the knot wraps around a torus meridianally and the q represents how many times the knot wraps around the torus longitudinally. We also decided to change these values, while keeping p and q relatively prime so as to not go from a knot to a link, to see if these knots would at least be externally tritangentless, and how their paths on a table would be affected.
p = 7 q =2
After exploring some of the variables and parameters surrounding rolling trefoil knots, we are excited to continue optimizing these knots by looking at other factors. In the future, we plan to optimize the materials, infill, and consistency in sizing of the knots to minimize differences not currently accounted for.
August 1, 2018 by lunaab1
Student Post: Programming Tilings with Escher
This post assumes that you have downloaded the KoebeLib repository and are using IntelliJ IDEA.
Escher is a domain specific language that was created to allow users to efficiently define and describe combinatorial subdivision rules and perform the subdivision. Today I will be showing you how to write a subdivision tiling program using Escher. Our tiling of choice for this tutorial is the well known Chair Tile (Figure 1).
Figure 1: The subdivision iterations of the geometric Chair Tile. [1]
Writing the Program
Figure 2: Sample code for a Chair Tile subdivision program in Escher
The first step in writing our subdivision program is to define all of the tiles that will be used (prototiles). Define a prototile using the keyword TILETYPE followed by an identifier for our tile and the number of vertices enclosed in {}. Note that the vertices created for a tile are indexed 0-N and connected sequentially into a cycle with N being connected to 1 and N-1. For our example we only have one prototile and it is defined on line 1.
TILETYPE chair {8};
Next, each prototile that is defined needs to have an accompanying set of subdivision rules. To define the subdivision rules for a specific prototile use the keyword SUBDIVISION followed by the name of the prototile. All of the subdivision rules need to be enclosed in a block designated by the {}. For our example we only need subdivision rules for the chair tile and they are defined in lines 2-21.
SUBDIVISION chair { INSERT RULES HERE };
Within a subdivision rule definition we can perform three main actions: splitting preexisting edges to created new vertices, creating new unconnected vertices, and specifying the child tiles. Creating a new vertex with the split function requires the keyword VERTEX followed by an identifier for the vertex, and equal sign, and the split function with the appropriate parameters. The three parameters for the split function are the origin and destination vertices for the desired edge and the number of edges you want to split that edge into. Note that for splits with edge counts larger than 2 you need to specify and identifier for each vertex that will be created when splitting the edge. For our example we split all of the edges on our Chair in lines 4-11. New unconnected vertices are created in lines 12-16.
VERTEX a = split(chair.vertex[0], chair.vertex[1], 2);
VERTEX b = split(chair.vertex[1], chair.vertex[2], 2);
VERTEX c = split(chair.vertex[2], chair.vertex[3], 2);
VERTEX d = split(chair.vertex[3], chair.vertex[4], 2);
VERTEX e = split(chair.vertex[4], chair.vertex[5], 2);
VERTEX f = split(chair.vertex[5], chair.vertex[6], 2);
VERTEX g = split(chair.vertex[6], chair.vertex[7], 2);
VERTEX h = split(chair.vertex[7], chair.vertex[0], 2);
VERTEX i;
VERTEX j;
VERTEX k;
VERTEX l;
VERTEX m;
The children in a set of subdivision rules are the resulting prototiles that are created by connecting newly created and existing vertices within the parent tile. To create a child rule use the keyword CHILD followed by and identifier for the child, an equal sign, and information about the resulting child tile: the tiletype followed by all of the vertices in counter-clockwise order encased in ([]). For our example we create four children of the chair tiletype in lines 17-20.
CHILD c1 = chair([chair.vertex[0], a, chair.vertex[1], j, i, m, chair.vertex[7], h]);
CHILD c2 = chair([chair.vertex[2], c, chair.vertex[3], d, k, j, chair.vertex[1], b]);
CHILD c3 = chair([i, j, k, d, chair.vertex[4], e, l, m]);
CHILD c4 = chair([chair.vertex[6], g, chair.vertex[7], m, l, e, chair.vertex[5], f]);
Finally we want to tell the program to execute the tiling. In order to do that we use the tile function and provide it with two parameters: the initial prototile and the number of subdivision iterations. Four our example we start with a chair tile and subdivide three times on line 22.
tile( chair, 3 );
Congratulations, you have successfully written your first Escher program. Save the file as chair.es and be sure to remember where you saved it.
Running the Program
In order to run the program locate the EscherDriver.kt file at KoebeLib/src/tiling/language/algorithms/EscherDriver.kt in the IntelliJ IDE and edit the run configurations. We need to add the full path of the Escher program file that we just saved into the Program arguments box. Now we can run the EscherDriver on our program by clicking the green triangle in the top right of the IDE. Running the driver will produce three files in the main KoebeLib directory: config, verts, and edges. These files will be used to visualize the tiling created by our program.
Visualizing the Results
In order to visualize the tiling we have created we will be using a python script that has been included in KoebeLib. Open a terminal and navigate to KoebeLib/src/tiling/language/algorithms/. Run the provided python script by typing python planarDraw.py this should display the tiling (Figure 3). This figure can be saved through the options at the bottom of the graph.
Figure 3: A graph of the Chair tiling after three iterations of subdivisions.
[1] Luis Blackaller, Piles of Tiles, http://black.mitplw.com/tiles/aperiodic.html
March 15, 2018 March 29, 2018 by mesechmg
Deutsch's Algorithm
The current posting is considered to be a simple example application of the theorems and mathematics discussed in the last post, The Basic Mathematics of Quantum Computing. The information here will be hard to grasp unless you have covered the operations specified previously. For this reason this post, and most postings following this, will be regarded as a continuation.
Deutsch's Algorithm is the one of the most representable quantum algorithms. This algorithm was developed in order to illustrate the processing of qubit input and the difference in performance when compared to a classical Turing machine. This algorithm covers the testing of black box functions, or modules of which the operations performed upon the input at the time of execution isn't known.
In this fashion, in order to determine how the black box executes we would have to test multiple inputs and examine patterns in the outputs. However, for this example we limit the possibilities used to only four boolean functions, two being balanced and two constant.
To clarify, a constant function has the same Boolean output for every input. While a balanced function yields as many 0s as it does 1s. We define our functions as such,
Both inputs of 0 and 1 map to the output 0 or 1 alike.
Both inputs of 0 and 1 map to the opposite output.
In the illustration below, functions one and three are constant, while two and four are balanced.
Normally, with a classic implementation we would need to test at least two inputs to determine if the function inside the black box was constant or balanced. Alternatively, using the principles of superposition on qubits we can evaluate both inputs at once to effectively cut our computational complexity in half.
The computational operations saved by using this algorithm may seem negligible, but when expanded into an algorithmic form the ability to evaluate data to this respect can have a quadratic decrease on the constant running time of a system.
Before learning about the procedure of the algorithm, it's important to review the mathematics needed in order to complete this excersise. If you recall from the last post we covered something known as the Hadarmad matrix, which is the quantum gate used to tranform a qubit into the state of superposition.
Recall: H .
Again this is done through matrix tensor multiplication.
It is important to remember that every qubit in any current state can be evaulated as a column vector made up of probabilites of possible occupying states. These column vectors representing the possible state positions of the qubits are represented as complex numbers where and each indicy belongs to the domain of complex numbers, such that .
Lets review the tensor multiplication of two qubits that contain real number probabilites. Such that has a 100% to occupy state 0 and has a 100% chance to occupy state 1. Next we apply the tensor product:
Once evaulated, he resulting qubit has four possible states but always has a 100% probabilty to be in the state 01.
Following this procedure we can apply the same operations between and the quantum gate H. Such that,
Hence, the resulting qubit has a complex probability of 50% being in state 0 and 50% of being in state 1. As shown previoulsy, if we wanted to evaulate these as real number probabilites we take the sqaure of the complex numbers.
Now that we have identified a basis for transitioning qubits into a state of superposition we are ready to evaulate Deutch's Algorithm. Recall, this is possible because of the qubits ability to occupy both testable inputs at once.
As we recognized, this algorithm consists of four black box functions with an input of one or zero and an output one or of zero. Again, if is balanced, otherwise if is constant.
Now consider the diagram below. First, notice that this graphic is a quantum circuit in which the two qubit inputs on the left are manipulated through the quantum gates denoted by H. They are then passed to the function which is our black box test.
From the diagram above we can see that by applying two qubits as the inputs and subsequently turning them both in a superposition, the value of the qubits becomes negligible as they have equal probability of being in both states.
We now explain the qubit state at each stage of the algorithm.
At we start with the initial separated qubit inputs
Next we examine state
First we must apply the matrix H to both our qubits, where
Finally we tensor together our two superposition qubits to achieve,
We use the tensor product to combine these two states to obtain the result .
Therefore the probability of qubit
This combined state can then be applied to our function as one input. We then evaualte the state of qubit as the output after having been applied to the black box function.
Here notice that the sign of this output changes dependent on which function was applied during execution, such that
From this expression we can see that depending on the values of we can determine whether the function is balanced or constant. This is because a constant function always yields
while a balanced always yields due to the change in sign.
Finally we can put this in terms of a piece wise function where the first qubit is the one that shows the attributes of the function and the second is the static transformation of the bottom qubit.
Recall that because H unitary, or its own inverse, we then effectively apply our last H to the top qubit in order to move it out of superposition for observation at and see the constraint on balanced or constant function.
We see this where
For clarification, the top qubit is the one that was manipulated by the function and brought out of a state of superposition, while the bottom qubit stayed statically bound to superposition in order to preserve the systems level of decoherence.
While this algorithm is simple, it still gives a tangible example of the applications of qubit mathematics and quantum computation. This procedure was later proven to be useful in determining the contents of many block box functions and can be implemented in a variety of different ways. Unfortunately, I cannot delve into all of the specific applications, as there are many other topics that needed to be covered. However, if you are interested in learning more, an extension of Deutsch's Algorithm is called the Deutsch-Jozsa Algorithm and can be applied to a much larger domain of input. In fact Deutsch's Algorithm serves as a basis for many algorithms in quantum computing that serve to expand upon evaluating multiple outputs at once.
Written By: Mitchell Mesecher
Quantum Computing for Computer Scientists, Noson S. Yanofsky