Options

Discrete calculus on a 3-diamond and the discrete heat equation in n-dimension

edited November 2018 in - - Computational methods

I've been writing a bunch of posts here on the Azimuth forum relating to noncommutative geometry and discrete calculus. I'm hoping that working things out in the open like this ultimately leads to some Azimuth blog posts and Azimuth wiki pages. For now, I'm still laying foundations and getting things straight in my own head.

I recently (re)discovered some very neat facts about the discrete heat equation. I hope to write up some of that material soon, but as a warm up, I extended the discrete calculus from (1+1)-dimensions used to describe the discrete Burgers equation to (2+1)-dimensions. The goal is to eventually get to (3+1)-dimensions and write down the discrete Navier-Stokes equations. This post can be considered background material for what is to come.

First of all, imagine the region of \(\mathbb{R}^3\) with all non-negative coordinates, i.e. \((x,y,z) = \mathbb{R}^3\) with \(x\ge 0\), \(y\ge 0\), and \(z\ge 0\). Now fill this region with cubes. Next, construct a directed graph from the cubes where each edge of each cube is directed toward increasing \(x\), \(y\), or \(z\) as illustrated below.

Finally rotate this directed graph so that the major diagonal \((1,1,1)\) is pointed in the \(z\)-direction. This is what I call a 3-diamond. Another good name for this might be "directed trinomial tree". It is the 3-dimensional version of the directed binary tree.

You will notice there are 3 edges directed into each interior node of the 3-diamond. When we rotate the cube into a diamond, there is a choice to be made as to how you want edges to be projected down onto the new \(x\) and \(y\) axes. The results are independent of the choice, but for concreteness, this is what I have chosen:

You can think of time as flowing up out of the page and a point in the 3-diamond is labeled \((x,y,t)\). The length of the projected edge is \(\Delta\) and the time that evolves from the start to the end of the edge is \(\Delta t\).

To help simplify the notation, I'll label the points according to

The differential of any discrete 0-form (i.e. function on nodes) \(f\) is given in terms of the graph coordinates via:

$$d f = (f_0 - f_1) \mathbf{e}^{10} + (f_0 - f_2) \mathbf{e}^{20} + (f_0 - f_3) \mathbf{e}^{30}.$$ Consequently,

$$d t = \Delta t (\mathbf{e}^{10} + \mathbf{e}^{20} + \mathbf{e}^{30})$$ ,

$$d x = \Delta \left(-\mathbf{e}^{10} + \frac{1}{2}\mathbf{e}^{20} + \frac{1}{2}\mathbf{e}^{30}\right)$$ and

$$d y = \Delta \left(-\frac{\sqrt{3}}{2}\mathbf{e}^{20}+\frac{\sqrt{3}}{2}\mathbf{e}^{30}\right).$$ These relations may be inverted resulting in

$$\mathbf{e}^{10} = \frac{1}{3}\left(\frac{1}{\Delta t} d t\right) - \frac{2}{3}\left(\frac{1}{\Delta} d x\right)$$ ,

$$\mathbf{e}^{20} = \frac{1}{3}\left(\frac{1}{\Delta t} d t\right) + \frac{1}{3}\left(\frac{1}{\Delta} d x\right) - \frac{1}{\sqrt{3}}\left(\frac{1}{\Delta} d y\right)$$ and

$$\mathbf{e}^{30} = \frac{1}{3}\left(\frac{1}{\Delta t} d t\right) + \frac{1}{3}\left(\frac{1}{\Delta} d x\right) + \frac{1}{\sqrt{3}}\left(\frac{1}{\Delta} d y\right).$$ With these, we could now write the differential \(d f\) in terms of \(d t\), \(d x\), and \(d y\). For now, I just want to focus on the time component, i.e. the coefficient of \(d t\)

$$d f = \left(\frac{3f_0 - f_1 - f_2 - f_3}{3\Delta t}\right) d t + (...) d x + (...) d y.$$ The time component vanishes when

$$f_0 = \frac{1}{3} \left(f_1 + f_2 + f_3\right).$$ Recall from the discrete Burgers equation revisited, we had the update expression

$$f_0 = \frac{1}{2} \left(f_1 + f_2 \right)$$ and showed that the continuum limit of this was the heat equation

$$\partial_t f - \frac{\eta}{2} \partial_x^2 f = 0.$$ Similarly, we could show the continuum limit of

$$f_0 = \frac{1}{3} \left(f_1 + f_2 + f_3\right).$$ is the (2+1)-dimensional heat equation.

Not only did we show that the limit is the corresponding heat equation, in (1+1)-dimensions we showed that the kernel of the discrete (1+1)-heat equation was the binomial PDF. Similarly, the kernel of the discrete (2+1)-heat equation is the trinomial PDF.

Hence, just as with the (1+1)-dimensional discrete heat equation, solutions mind bogglingly become more accurate as you evolve them in time because the kernels converge, solutions to the (2+1)-dimensional heat equation will also mind bogglingly converge as you evolve them in time because the trinomial PDF is known to converge to the bivariate normal PDF.

This generalizes to \(n\)-dimensions on \((n+1)\)-diamonds. The kernel of the \((n+1)\)-dimensional discrete heat equation

$$f_0 = \frac{1}{n+1} \left(\sum_{i=1}^{n+1} f_i\right)$$ is the multinomial PDF.

This is mind boggling to me even if it is not too surprising and unlikely to be new.

Comments

  • 1.
    edited May 2011

    Was thinking about this while on a jog just now...

    The discrete heat equation in $(n+1)$-dimensions

    $$f_0 = \frac{1}{n+1} \left(\sum_{i=1}^{n+1} f_i\right)$$ says that the value at the center of a regular $n$-simplex at time $t = 0$ is the average of the values on the $n+1$ nodes of the regular $n$-simplex at the earlier time $t = -\Delta t$.

    This reminds me of the well-known fact about Laplace's equation (from Mathworld)

    A solution to Laplace's equation has the property that the average value over a spherical surface is equal to the value at the center of the sphere (Gauss's harmonic function theorem).

    This temps me to make the following claim:

    A solution to the heat equation has the property that the average value over a spherical surface is equal to the value at the center of the sphere at a later time determined by the radius and diffusion coefficient.

    I would be depressed for a whopping 5 minutes if this claim turns out to be false. If it is true, that would be interesting. Anyone have an idea? Care to try to prove/disprove the claim?

    Comment Source:Was thinking about this while on a jog just now... The discrete heat equation in $(n+1)$-dimensions $$f_0 = \frac{1}{n+1} \left(\sum_{i=1}^{n+1} f_i\right)$$ says that the value at the center of a regular $n$-simplex at time $t = 0$ is the average of the values on the $n+1$ nodes of the regular $n$-simplex at the earlier time $t = -\Delta t$. This reminds me of the well-known fact about Laplace's equation (from [Mathworld](http://mathworld.wolfram.com/LaplacesEquation.html)) >A solution to Laplace's equation has the property that the average value over a spherical surface is equal to the value at the center of the sphere (Gauss's harmonic function theorem). This temps me to make the following claim: >A solution to the heat equation has the property that the average value over a spherical surface is equal to the value at the center of the sphere at a later time determined by the radius and diffusion coefficient. I would be depressed for a whopping 5 minutes if this claim turns out to be false. If it is true, that would be interesting. Anyone have an idea? Care to try to prove/disprove the claim?
  • 2.

    A solution to the heat equation has the property that the average value over a spherical surface is equal to the value at the center of the sphere at a later time determined by the radius and diffusion coefficient

    I believe this claim is false: this claim is equivalent to saying that the Green's function $G(t,\mathbf{x})$ for the heat equation is supported on some sphere $\|\mathbf{x}\| = r$ where $r$ depends on $t$ (or as you say, $t$ depends on $r$). But the Green's function for the heat equation is a Gaussian in $\mathbf{x}$ for any fixed $t$.

    On the other hand (giving you five minutes to get over being depressed) a claim rather similar to this is true for the wave equation.

    Comment Source:> A solution to the heat equation has the property that the average value over a spherical surface is equal to the value at the center of the sphere at a later time determined by the radius and diffusion coefficient I believe this claim is false: this claim is equivalent to saying that the Green's function $G(t,\mathbf{x})$ for the heat equation is supported on some sphere $\|\mathbf{x}\| = r$ where $r$ depends on $t$ (or as you say, $t$ depends on $r$). But the Green's function for the heat equation is a Gaussian in $\mathbf{x}$ for any fixed $t$. On the other hand (giving you five minutes to get over being depressed) a claim rather similar to this is _true_ for the wave equation.
  • 3.

    Eric, if you come up with a new numerical scheme for the Navier-Stokes equations, I'll certainly find the time to implement it for a 3D simulation, as I have had it on my TODO-list for quite some time now.

    A long term project is still a simulation of a cube with periodic boundary conditions via the (spatial) spectral method.

    Comment Source:Eric, if you come up with a new numerical scheme for the Navier-Stokes equations, I'll certainly find the time to implement it for a 3D simulation, as I have had it on my TODO-list for quite some time now. A long term project is still a simulation of a cube with periodic boundary conditions via the (spatial) spectral method.
  • 4.

    You're right. The claim is false and I've already recovered enough to make a new claim :)

    My mistake was a poor extrapolation of something that is true infinitesimally.

    I think you can recover the heat equation from a solution to the heat equation by integrating the solution over the surface of the sphere and relating it to the value at the center of the sphere at a later time determined by the radius of the sphere and the diffusion coefficient in the limit as the radius of the sphere goes to zero.

    Comment Source:You're right. The claim is false and I've already recovered enough to make a new claim :) My mistake was a poor extrapolation of something that is true infinitesimally. I think you can recover the heat equation from a solution to the heat equation by integrating the solution over the surface of the sphere and relating it to the value at the center of the sphere at a later time determined by the radius of the sphere and the diffusion coefficient _in the limit as the radius of the sphere goes to zero_.
  • 5.
    edited June 2011

    That might be right. What I know is that a solution of the heat equation at any time and any point in space can be recovered by integrating that solution multiplied by a suitable Gaussian over all of space at some previous moment in time. The suitable Gaussian is called the 'heat kernel' and you can see it here. Some statement like yours should arise by taking a limit as the difference in times approaches zero. Indeed this limiting statement should just be a way of saying

    $$ \frac{d f}{d t} = const \; \nabla^2 f $$

    Comment Source:That might be right. What I know is that a solution of the heat equation at any time and any point in space can be recovered by integrating that solution multiplied by a suitable Gaussian over all of space at some previous moment in time. The suitable Gaussian is called the 'heat kernel' and you can see it [here](http://en.wikipedia.org/wiki/Heat_kernel). Some statement like yours should arise by taking a limit as the difference in times approaches zero. Indeed this limiting statement should just be a way of saying $$ \frac{d f}{d t} = const \; \nabla^2 f $$
Sign In or Register to comment.