Partial differential equations on graphs

During the summer and fall of 2016, Annie Rak did some URAF (a program formerly called HCRP) on partial differential equations on graphs. It led to a senior thesis in the applied mathematics department. Here is a project page and here [PDF] were some notes from the summer. The research of Annie mostly dealt with advection models on directed graphs (digraphs).

As partial differential equations in general relate to diffusion process, this happens also here. The stochastic process is the Markov dynamics defined on the graphs. The advection model for a directed graph $G$ is $u' = -Lu$ , where $L={\rm div} V {\rm grad}_0 u$ is the directed Laplacian. As in the usual Laplacian $L=d^*d$ for undirected graphs which leads to the heat equation $u' = -Lu$ , the advection Laplacian uses difference operators: the modification of the gradient ${\rm grad}_0$ which is the minimum of ${\rm grad}$ and $0$ . The divergence ${\rm div}=d^*$ as well as ${\rm grad}=d$ are defined by the usual exterior derivative $d$ . The consensus model is the situation, where the graph $G$ is replaced by its reverse graph $G^T$ , where all directions are reversed. One can therefore easily focus on advection. The advection dynamics relates to Markov chains: If $L=D-A$ , then $M=A D^{-1}$ is a left stochastic matrix, a Markov operator, which maps probability vectors to probability vectors. The kernel of $L$ is related to the fixed points of $M$ . Assume $L D^{-1} u=0$ , then $(D-A) D^{-1} u=0$ and $u=A D^{-1} u = Mu$ . Perron-Frobenius allows to study the structure of the equilibria or equivalently the kernel of $L$ .

Lets look at the kite graph. The Laplacian of $G$ is $L=B-A= \left[ \begin{matrix} 3 & -1 & -1 & -1 \\ -1 & 2 & 0 & -1 \\ -1 & 0 & 2 & -1 \\ -1 & -1 & -1 & 3 \end{matrix} \right]$ = $\left[ \begin{matrix} 3 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \\ \end{matrix} \right]$ – $\left[ \begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{matrix} \right]$ , where $A$ is the incidence matrix. When equipped with an orientation $G$ is a digraph. Given the orientation, the incidence matrix is the $4 \times 5$ matrix ${\rm div} = D_{a,e(b)}$ which is $1$ if the arrow between $a,b$ points towards $a$ and $-1$ else. It is the discrete analogue of the divergence. The $5 \times 4$ matrix ${\rm grad} = D^*$ is the gradient. Now, ${\rm div} \circ {\rm grad}$ is the Laplacian: $\left[ \begin{matrix} -1 & 0 & 1 & & 1 \\ 1 &-1&0&0&0 \\ 0&1&-1&-1&0 \\ 0&0&0&1&-1 \\ \end{matrix} \right]$ $\left[ \begin{matrix} -1 & 1 & 0 &0 \\ 0 & -1 & 1 & 0 \\ 1&0&-1&0 \\ 0 &0&-1&1 \\ 1&0&0&-1 \\ \end{matrix} \right]$ = $\left[ \begin{matrix} 3&-1&-1&-1 \\ -1&2&-1&0 \\ -1&-1&3&-1 \\ -1&0&-1&2 \\ \end{matrix} \right]$ .

The gradient of the directed graph contains only the incoming $1$ entries. The modified Laplacian is $L_0={\rm div} \circ {\rm grad}_0$ . Again it is of the form $B-A$ , where $B$ is the diagonal incoming vertex degree diagonal matrix and $A$ is the adjacency matrix $A_{ij}=1$ if $i \to j$ .
Both matrices $L$ and $L_0$ have the property that the sum of each column entries is constant $0$ . This means that $L^T, L_0^T$ have the eigenvector $\langle 1, \dots 1 \rangle$ with eigenvalue $0$ . So, also $L_0$ has an eigenvalue $0$ .

We can write $L_0 = B_0 - A_0$ , where $B_0$ is the diagonal part and $A_0$ the off diagonal part. Now, in the case when all incoming vertex degrees are nonzero, we can invert $B_0$ and form $M_0 = -A_0 B_0^{-1}$ . This is a stochastic matrix in the sense that all entries are non-negative in $[0,1]$ and that the sum over all column entries is equal to $1$ . These are now transition probabilities.

The heat equation is $u' = -L u$ . The wave equation is $u''=-L u$ . The advection equation is $u'=-L_0 u$ . Now, while $L$ is symmetric and has non-negative real eigenvalues, the matrix $L_0$ can have complex eigenvalues. In the kite example, the eigenvalues of $L$ are $\{4,4,2,0 \}$, the eigenvalues of the directed graph with a loop $L_1$ are $\{ 0,(3 + i \sqrt{3})/2,(3 - i \sqrt{3})/2,2 \}$ , the spectrum of $L_2$ is $\{ 3,1,1,0 \}$ .

Author: oliverknill