# Heat equation on a finite graph and computing a ratio

Let $$\Delta$$ denotes the Laplace operator with $$-\Delta \phi = \lambda\phi$$ on the compact manifold $$(M,g)$$. In a paper it is stated that the solution of the heat equation

\begin{align} (\partial_t - \Delta)u(t,x) &= 0 \\ u(0,x) &= f(x), \end{align}

is given by $$e^{t\Delta}f$$. This includes a heat kernel $$p(t,x,y)$$ satisfying

\begin{align} [e^{t\Delta}f](x) = \int_M p(t,x,y)f(y)d \end{align}

where $$p(t,x,\cdot)$$ is a probability distribution. My questions about this are as follows:

1. Would you recommend me a reference which concisely described the heat equation on graph (preferred to be in a simple and intuitive approach) and how to solve that? (Of course, that is great if someone can elaborate on the derivation of solution for the heat equation on graph.)

2. Let $$v$$ be a vector and let $$t=t_0$$ be known. Based on a paper, I need to calculate $$\|e^{t\Delta}(v)\|/\|v\|$$ on a finite graph. I am in doubt about my way to compute this ratio. I computed $$e^{t\Delta}$$ on the graph by diagonalization and then multiplication by $$v$$. It is denoted in the paper that the ratio must be in the range $$[0,1]$$, but after coding, the obtained ratios have values out of this range. Did I this computation correctly?

• In the eigenvalue/vector relation there is a 'minus' behind the laplace operator whereas we consider for the Laplacian ($$L$$) as $$L\phi = \lambda \phi$$ without that minus. I guess that might provide the problem. Do we need a minus the in the power? (by curiosity, I put a minus and the range gets $$[0,1]$$)

Thanks.

• I did that once but with matrices. Would that approach be helpful to you? – Rócherz Feb 20 at 1:56
• @Rócherz: that might be useful. Please go ahead. – Amin Feb 20 at 1:59

(Disclaimer: I'm not a Physicist, and I kind of suck at explaining today.)

Consider the heat equation over a finite convex subset of $$\mathbb R^N$$ and with initial values at $$t=0$$. We may desire to approximate the analytical solution with numerical methods, and for that purpose, we shall think of a collection of $$n$$ points on the domain space, with heat flowing between them. Some of these points shall be assumed to be somewhat connected to others (usually on the grounds of proximity and symmetrical flow), as to allow heat flow, so it is reasonable to think of our points as the vertices of a connected, unweighted simple graph. We usually select graphs with nice structures such as lines, rings, grids, et cetera. Now consider a vector function $$f : [0,\infty) \to \mathbb R^n$$ where $$f(t)$$ is a vector comprising the values of the heat function on all vertices at a given time $$t$$. We may decree a bijection between the vertices and a set of indeces $$\{1, \ldots, n\}$$ just to save some time.

Let $$L$$ be the Laplacian matrix of our graph ($$L$$ has entries $$L_{i,i} =\deg i$$ for vertex $$i$$, $$L_{i,j}=-1$$ if edge $$ij$$ exists, and zeroes elsewhere). Then the heat function can be approximated with the solution of $$\dot f =-L\,f,$$ where $$f(0)$$ is given (taken from the initial values.) Matrix $$L$$ happens to be semi-definite positive and real symmetrical, so it has an eigendecomposition $$L=Q\Lambda Q^{\rm T}$$ where the columns of $$Q$$ are eigenvectors of $$L$$ that are asociated to the diagonal entries of $$\Lambda$$. For a connected graph, the scalar $$0$$ is an eigenvalue to $$L$$ with just multiplicity one, asociated to the (normalized) all-ones vector $$(1/\sqrt{n}) \, \vec 1$$.

Now, the original matrix equation cannot be solved since the rows are related. However, a change of variable makes them unrelated: $$\dot f =-L\,f =-Q\Lambda Q^{\rm T}f \Longrightarrow Q^{\rm T}\dot f =-\Lambda Q^{\rm T}f.$$ Let $$g=Q^{\rm T}f$$, then our matrix differential equation becomes $$\dot g =-\Lambda g$$ with initial values $$g(0)=Q^{\rm T} f(0)$$. Since $$\Lambda$$ is diagonal, the matrix equation becomes a set of $$n$$ non-related first-order differential equations $$\dot g_i =-\lambda_i g_i$$, where the $$\lambda_i$$ are the eigenvalues of $$L$$, sorted monotonically increasing on $$i$$. For $$\lambda_1=0$$ we just have $$\dot g_1=0$$, so $$g_1(t)$$ is just $$g_1(0)$$; but we can rewrite it as $$g_1(t) = e^{-\lambda_1 t} g_1(0)$$ so as to match the rest of the $$g_i(t) = e^{-\lambda_i t} g_i(0)$$. Building the whole vector $$g$$: $$g(t) =\exp(-\Lambda t) g(0).$$ Reverting the change of variable gives $$f(t) = Q \exp(-\Lambda t) Q^{\rm T} f(0).$$

• How can a subset of $\mathbb{R}^N$ be finite, convex, and have more than one element? (I think I more or less understand what you meant, but as stated that makes no sense.) – Ian Feb 20 at 3:11
• Tried to avoid infinite domains or gaps within. Just "closed subset", then? – Rócherz Feb 20 at 3:23
• @Rócherz: you actually reach the Hamiltonian operator. Another point is that what is your idea about computation of that ratio in my question? Do you agree with me? – Amin Feb 20 at 3:28
• @Amin: I do agree. – Rócherz Feb 20 at 3:57
• @Amin: I had the guidance of my grad school thesis advisor to derive it. I humbly reckon it may actually be textbook material for matrix differential equations, which I haven't taken a single course ever. But if you can either figure out or look out how to solve $\dot f = A\,f$ for positive definite $A$, then you can adapt it to symmetric negative semidefinite $A=-L$. – Rócherz Feb 20 at 11:13