discrete laplace operator

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, but defined so that it has meaning on a graph or a discrete grid.

Definition

Let G=(V,E) be a graph with vertices V and edges E. Let

\phi:V\rightarrow\mathbb{C}

be a function mapping vertices to complex numbers. Then, the discrete Laplacian

\Delta

acting on

\phi

is defined by

(\Delta\phi)(v)=\sum_{w:\textrm{dist}(w,v)=1}\phi(w)-\phi(v)

where

\textrm{dist}(w,v)

is the distance operator on the graph. Thus, this sum is over the nearest neighbors of the vertex v. If the graph has weighted edges, that is, a weighting function

\gamma:E\rightarrow\mathbb{C}

is given, then the definition can be generalized to

(\Delta_\gamma\phi)(v)=\sum_{w:\textrm{dist}(w,v)=1}\gamma_{wv}(\phi(w)-\phi(v))

where

\gamma_{wv}

is the weight value on the edge

wv\in E

Theorems

If the graph is a square lattice grid, then this definition of the Laplacian can be shown to correspond to the continuous Laplacian in the limit of an infinitely fine grid. Thus, for example, on a one-dimensional grid we have

\frac{\partial^2F}{\partial x^2} =

\lim_{\epsilon \rightarrow 0}

   \frac{(F(x+\epsilon)-F(x))+(F(x-\epsilon)-F(x))}{\epsilon^2}.

This definition of the Laplacian is commonly used in numerical analysis and in image processing. In image processing, it is considered to be a type of digital filter, more specifically an edge filter, called the Laplace filter.

Discrete Schrdinger operator

Let

P:V\rightarrow\mathbb{R}

be a potential function defined on the graph. Note that P can be considered to be a multiplicative operator acting diagonally on

\phi

(P\phi)(v)=P(v)\phi(v).

Then

H=\Delta+P

is the discrete Schrdinger operator, an analog of the continuous Schrdinger operator. If the number of edges meeting at a vertex is uniformly bounded, and the potential is bounded, then H is bounded and self-adjoint. The spectral properties of this Hamiltonian can be studied with Stone's theorem; this is a consequence of the duality between posets and boolean algebras.