On first read, I understand that simply the title of my new paper – "A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians" - can be quite daunting. Believe me, I am aware that terms such as multigrid, Fiedler, and vector are not words that people use in their daily lives. With that said, if you would like to understand what exactly this paper is about, the title is a good place to start!
A screenshot of John Urschel's paper as seen on the website of the Journal of Computational... [+]
First, I need to do some backtracking. I need to define what a graph is. Think I’m crazy? Insulting your intelligence? You took high school math, and drew graphs all the time! Well, I hate to be the bearer of bad news, but we are not talking about those types of graphs. This is not the graph of a function, and we certainly are not working in the Cartesian plane. By graph, we are referring to a set of discrete objects and the relationships between them. Did I lose you? Don’t worry. Believe it or not, you are a part of a graph. Consider Facebook; let us take all the users of Facebook and say that two users are related if they are friends. Not only did we just define a graph, but we defined one in which you are one of the discrete objects! (Facebook defines it this way, too – it calls all its users’ relationships a "social graph.")
Graphs are used in all sorts of applications, ranging from computer science to linguistics, to biology, to physics, even sociology, and just about everything in between. Anywhere where there a discrete objects and some kind of relationship between them, graphs are likely to be found.
Now, let’s look at the word vector. This definition can be tough. Formally in mathematics, a vector is an element of something called a vector space. More informally, it can be thought of some quantity in a given space with a magnitude and a direction. (In football, a vector would be the direction of a receiver’s route and how fast he’s running.) For our purposes, we can just call it an ordered collection of numbers.
So what’s a Fiedler vector? This refers to the famous mathematician Miroslav Fiedler, who proved many results in the area of matrix algebra and other mathematical fields. He is most famous for proving a number of results on a vector that quantifies certain properties of graphs. For that reason, this vector was aptly named the Fiedler vector (I can only hope someone names such a thing after me). In one of my previous papers, and in my opinion, my biggest contribution to math to date, I extend and effectively end the conversation on some of the results he proved. You can find the abstract to that paper here.
What the Fiedler vector does is it assigns a number to each discrete object, so that if two objects are related, they are likely to be close in number. (This is just like football, by the way. Jersey numbers are assigned within a certain range based on their position.) The usefulness of such an assignment may not seem obvious at first. But let’s say you had a graph with thousands of discrete objects, and within that graph you had subgroups of hundreds of related objects. If you wanted to sort those objects out, you’d ideally want to want to divide it so that all the closely related objects were together, with as few relations to other parts of the graph as possible. This is referred to graph partitioning, or graph clustering. The Fiedler vector has proven to be a very good way to efficiently partition a graph into parts.
Now we’re left with only one more word to define: multigrid. Multigrid is a class of numerical techniques used to approximately solve complicated math problems (typically elliptic partial differential equations). These kinds of problems appear in everything from physics to biology to economic models. The beauty of multigrid is that it uses a multi resolution scheme to try to minimize the error on each level, thus minimizing the global error much faster than trying to solve the problem outright.
In my latest paper, I developed a type of multigrid method in which the Fiedler vector is solved for on a variety of different ‘coarse’ graphs. The coarse graphs were simpler approximations of an original, more complex graph which I was trying to compute the vector for. Basically, I was looking for a way to use simpler graphs to come up with approximate solutions that are close to the exact solution of the complex graph. Under ideal circumstances, I showed my technique to be uniformly convergent, meaning that it works well independently of the size of the problem. I was also able to provide numerical results that show my new method performs very well in comparison to other existing techniques. I won’t spoil too many of the details. That’s for you to read about!
Now that we’ve made it through the title of my paper, hopefully you’ve had some fun and learned just a little bit more about mathematics. Now you’re ready to tackle the whole thing. Best of luck!
