This example demonstrates a practical use for extreme eigenvalues. The aim is to partition the vertices of a mesh/graph into two subdomains, with each part having roughly equal numbers of vertices and with the partition cutting through as few edges as possible. (An edge is cut if its two vertices lie in each of the two subdomains.) One way to partition a graph is to form the Laplacian and use its Fiedler vector (the eigenvector that corresponds to the second smallest eigenvalue) to order the vertices. There are more efficient algorithms for graph partitioning that do not require the calculation of the eigenvector, but the approach using Fiedler remains an important one.

This is the data for the coordinates of the vertices

In[1]:=

This is a list of triangles that forms the mesh.

In[2]:=

To plot the mesh, simply plot each of the triangles.

In[4]:=

A Laplacian of a graph, , is an sparse matrix, with the number of vertices in the graph. The entries of are mostly zero, except that the diagonals are positive integers that correspond to the degree of the vertex, where the degree is the number of vertices linked to the vertex. In addition, if two vertices, and , are joined by an edge, the entry is -1.

For the mesh here, the off-diagonals are given by the sparse array M.

In[10]:=

Out[11]=

Each diagonal in a row is the negated sum of the off-diagonals. Thus the diagonal part of matrix is as follows.

In[12]:=

Out[12]=

Therefore, the Laplacian is given as below.

In[13]:=

Out[13]=

This loads the MatrixPlot function and visualizes the matrix.

In[14]:=

The sum of each row is zero, therefore the Laplacian matrix is positive semi-definite with a zero eigenvalue. The eigenvector corresponding to the second smallest eigenvalue is called the Fiedler vector.

This calculates the two smallest eigenvalues and eigenvectors.

In[16]:=

One of these eigenvalues is zero.

In[17]:=

Out[17]=

Now use the Fiedler eigenvector to generate an ordering of vertices and form two groups of vertices: domain1 and domain2.

In[18]:=

This sets the colors of vertices in domain1 as Hue[0.] (red) and vertices in domain2 as Hue[0.75] (blue).

In[21]:=

This plots the partition. As can be seen, the partitions avoided the very dense part of the mesh, and each subdomain is nicely connected.

In[23]:=

The number of edges cut by the partition can be calculated as follows.

In[26]:=

Out[28]=