Independent Study

This semester I have decided to do an independent study with Professor Jeff Erickson.

The project we are working on (like several of the projects I have worked on in the past) involves numerical simulations of physical systems. Consider a function F(x,t) which represents the value of a particular physical variable at a particular point in space (x) at a given time (t). For example, in an application modeling heat transfer, F could represent the temperature at a given point in the material. The function F is defined by a set of initial conditions (at t=0) and then a set of differential equations that define how the value of F at each point x changes over time. The goal is to calculate (or at least estimate) the values of F over time.

Of course there are an infinite number of different values of X, and so an infinite number of variables to track. In order to solve this problem it is necessary to divide the region of interest up into a large number of smaller "cells," and keep track of one value at each cell. The pattern of cells is referred to as a "mesh". In a one dimensional case the "mesh" is trivial, but in a two dimensional problem there are lots of different mesh patterns, such as a square grid or a triangular grid. (I worked on a project with exactly this theme several years ago.)

One way of understanding the point of the "mesh" is by analogy to wargames like Dungeons + Dragons. In a real battle, movement is continuous, but in the game it is necessary to approximate that continuous movement by a discrete grid. And the shape of that grid (square in D+D, hexagonal in many other war games) is like the "mesh", and each point in that mesh is dealt with separately.

Of course in real life time is also continuous, so there are an infinite number of points in time. So just like with space, it is necessary to approximate the continuous time interval with a set of discrete points in time.The standard way of solving these problems doing this is to choose a "time step" dt - so for example if dt=6 seconds, you calculate the values of F at t=6 based on the values at t=0, then repreat the process to get the values at t=12 from t=6, and so on. (To continue with the D+D analogy, in a real life battle things are happening continuously in real-time, but the game divides up the time into a series of discrete "combat rounds".)

Now we come to the main part of our project. The part of our project that is different is to, rather than choose a mesh once and do a series of iterations where the time increases by dt each time, you keep track of a separate value of t for each vertex in the mesh, and increase the t value one vertex at a time. The advantage of doing this is that in many applications, there's a known maximum speed at which effects can propagate, and you can use this to limit the number of simultaneous equations that it is necessary to solve. Suppose that the equations are modeling sound waves, and the speed of sound in the material in question is 1000 meters per second, and suppose that the cells are spaced 1 meter apart. Then if, you use a dt of 0.001 seconds, then in one time step effects can propagate at most one mesh cell, so at each step rather than having to solve simultaneous equations for all the cells in the mesh, you only have to do so for one cell and its nearest neighbors, because those are the only cells that can affect the given vertex. This can significantly speed up the algorithm, and it also allows you to take better advantage of multiple processors, because different processors can be working on different parts of the mesh.

As for the D+D analogy for that, this is more of a stretch but here goes. Let's say you have a gigantic battle with 100 different characters arranged in a 10x10 array, and let's say each character only has powers that can affect other characters adjacent to him, and none of them can move.* Of course this battle is going to be slow going because once one person declares his actions he has to wait for 99 other characters to declare their actions before they can go do them and start theire next round. But as it turns out you don't need to keep everyone in sync like that - you can have some players start their second and subsequent rounds even before everyone finishes their first round. This is possible for the slow speed of interaction - since it will take nine rounds for anything happening in, say, the top left corner of the board to affect the character in he bottom right corner, one of those corners can be up to nine rounds "ahead" of the other and the game will still work just as normal. Basically, let's say that the guy in the top left corner just finished his 10th round while the guy in the bottom right corner is still deciding on his action for the 5th round. This will still work because the bottom right guy's 5th round action won't affect the first guy until at least the 14th round (it has to get through nine intervening spaces at one space per round), so he doesn't need to know about it yet. The condition that the "time difference" between two cells is no greater than the time it takes for information to move between them is known as the "causality" constraint.

However, there is an important complication. It is possible in certain circumstances, depending on how the mesh is laid out, to get "stuck" - i.e. there is no way to progress any vertex without violating a causality constraint.** If this happens then you have to (at least temporarily) go back to the original method of pushing up all the vertices at once*** (this is analogous to having everyone take their turns in sync, in the previous analogy). The problem is how to progress in such a way that you avoid getting stuck. There are also lots of other complications, like it you want to refine (i.e. make denser) a part of the mesh in the middle of the program execution, etc.

There is already a program that does this, and a paper about it, for the case of two dimensional meshes. The part that remains to be done is doing this for three dimensional meshes. Some of the algorithm design work is already done so a lot of the work is just coding it up (but after that we'll get to the other parts where the algorithms that are needed are not known yet).

In Erickson's words, "most computer science Ph.D. students can't program their way out of a wet paper bag, and that applies to most computer science professors as well.****" Since I am not one of those "most computer science Ph.D. students" he thought it would be a good idea for me to work for him.

---

* This analogy is technically inaccurate because in D+D, each player's turn happens sequentially, so A can do something to affect B, then that affects what B does, which affects C, so C chooses an action which affects D, and so on, all in the space of one round. For this analogy to work you have to assume that all turns happen simultaneously so that each link in the chain requires another round.

** It might appear that it is never possible to get stuck - if you increment the t value on the vertex that currently has the lowest t value, then you're not increasing any gaps. The explanation is that my description is significantly simplified - in reality it's not actually about the difference between the t values of the vertices, it has to do with the slopes of the sides of the "cells" in the n+1 dimensional space consisting of the n space dimensions plus the time dimension. But I couldn't figure out how to explain that part concisely and this post is long enough as it is.

***I'm actually not 100% sure how this part works. I just talked to Erickson yesterday and haven't read the papers yet.

****Erickson is not the first of my professors to express a similar sentiment. University of Maryland professor Samir Khuller said that when people find out that he is a computer science professor, sometimes that ask him to help fix their computer, and he says that "I can't even fix my own computer, how can I fix yours?" Michelle Hugue even once said that she "hates computers."