The discrete Laplacian matrix

linear-algebra, math

There is a nice and compact way of writing the discrete NN-d Laplacian matrices on a uniform grid. I’ve found these expressions particularly useful in practice; for example, when testing a linear solver via solving Poisson’s equation Δu=f\Delta u = f, one benefits from having a quick way of constructing the matrix on the left-hand side.

Kronecker product

First, we need to introduce the Kronecker product. If AA is an m×nm \times n matrix and BB is a p×qp \times q matrix, then the Kronecker product ABA \otimes B is the pm×qnpm \times qn block matrix

AB=(a11Ba1nBam1BamnB).A \otimes B = \begin{pmatrix} a_{11}B & \cdots & a_{1n}B \cr \vdots & \ddots & \vdots \cr a_{m1}B & \cdots & a_{mn}B \end{pmatrix} .

I see this as distributing BB to the elements of AA.

2D discrete Laplacian matrix

Let Δ\Delta be the three-point approximation to the 1D Laplacian with homogeneous Dirichlet boundary conditions on a uniform grid with grid spacing hh, i.e., the tridiagonal matrix

Δ=1h2(2100121001200002).\Delta = \frac{1}{h^2} \begin{pmatrix*}[r] -2 & 1 & 0 & \cdots & 0 \\ 1 & -2 & -1 & \cdots & 0 \\ 0 & 1 & -2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -2 \end{pmatrix*} .

Then, for a uniform 2D grid with grid spacing hh of size m×nm \times n in lexicographic storage order, the discrete 2D Laplacian with homogeneous Dirichlet boundary conditions can be written as

ImΔn+ΔmIn,I_m \otimes \Delta_n + \Delta_m \otimes I_n ,

where the subscripts on II, the identity matrix, and Δ\Delta indicate the size of those square matrices. Note that hh is embedded in the definition of Δ\Delta.

3D discrete Laplacian matrix

Similarly, for a uniform 3D grid with grid spacing hh of size m×n×pm \times n \times p in lexicographic storage order, the discrete 3D Laplacian with homogeneous Dirichlet boundary conditions can be written as

ImInΔp+ImΔnIp+ΔmInIp.I_m \otimes I_n \otimes \Delta_p + I_m \otimes \Delta_n \otimes I_p + \Delta_m \otimes I_n \otimes I_p .

NN-d discrete Laplacian matrix

The formulas above generalize to NN dimensions. For a uniform NN-d grid with grid spacing hh of size m1×m2××mNm_1 \times m_2 \times \cdots \times m_N in lexicographic storage order, the discrete NN-d Laplacian with homogeneous Dirichlet boundary conditions can be written as

i=1N(j=1i1Imj)Δmi(j=i+1NImj).\sum_{i=1}^N \left( \bigotimes_{j=1}^{i-1} I_{m_j} \right) \otimes \Delta_{m_i} \otimes \left( \bigotimes_{j=i+1}^N I_{m_j} \right) .

© 2024 Peter Cheng