{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Finite Difference Operators in Many Dimensions using Kronecker Products\n", "**Prof. Tony Saad (www.tsaad.net)
Department of Chemical Engineering
University of Utah**\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is very easy to build complex 2D and 3D finite difference operators using Kronecker products. We will start by defining a basic forward difference operator for the first derivative. We can choose other operators as well, but this particular case produces tight stencils for Laplacians.\n", "\n", "The forward difference is given by\n", "\$$\n", "\\frac{\\text{d}u}{\\text{d}x} = \\frac{u_{i+1} - u_{i}}{\\Delta x}\n", "\$$\n", "\n", "In operator form, and for a periodic case on a 1D grid, this operator looks like\n", "\$$\n", "\\mathbf{D}^+ =\n", "\\left[ {\\begin{array}{*{20}{c}}\n", "{ - 1}&1&{}&{}&{}\\\\\n", "{}&{ - 1}&1&{}&{}\\\\\n", "{}&{}&{ - 1}&1&{}\\\\\n", "{}&{}&{}&{ - 1}&1\\\\\n", "1&{}&{}&{}&{ - 1}\n", "\\end{array}} \\right]\n", "\$$\n", "\n", "For periodic boundaries, this operator can be defined in Python as\n", "Python\n", "def d_plus(n, dx=1):\n", " # periodic forward difference\n", " d = np.ones(n, dtype=int)\n", " ud = np.ones(n-1, dtype=int)\n", " D = diag(-d) + diag(ud,1)\n", " D[-1,0] = 1\n", " return D/dx\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will also need a backward difference operator, $\\mathbf{D}^-$, to enable us to compute second derivatives and Laplacians. It can be shown that $\\mathbf{D}^-$ is given by the negative of the transpose of $\\mathbf{D}^+$\n", "\$$\n", "\\mathbf{D}^- = - \\mathbf{D}^{+T}\n", "\$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Two-Dimensions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To construct forward and backward difference operators for an entire 2D grid, we can using the Kronecker product. For a uniform structured grid of size $N_x \\times N_y$ we can construct four operators: $\\mathbf{D}_x^+$, $\\mathbf{D}_x^-$, $\\mathbf{D}_y^+$, $\\mathbf{D}_y^-$ where the subscript refers to the direction in which the derivative is taken, e.g. $\\mathbf{D}_y^+ u= \\frac{\\partial u}{\\partial y}$ represents the forward difference approximation of $\\frac{\\partial u}{\\partial y}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Kronecker product, defined via the symbol $\\otimes$, is simply a way to produce matrices based on matrix outer products. Given matrices $\\mathbf{A} = a_{ij}$ and $\\mathbf{B} = b_{ij}$, then\n", "\$$\n", "\\mathbf{A}\\otimes\\mathbf{B} = \\begin{bmatrix} a_{11} \\mathbf{B} & \\cdots & a_{1n}\\mathbf{B} \\\\ \\vdots & \\ddots & \\vdots \\\\ a_{m1} \\mathbf{B} & \\cdots & a_{mn} \\mathbf{B} \\end{bmatrix}\n", "\$$\n", "\n", "An example from Wikipedia is\n", "\n", "\$$\n", " \\begin{bmatrix}\n", " 1 & 2 \\\\\n", " 3 & 4 \\\\\n", " \\end{bmatrix}\n", " \\otimes\n", " \\begin{bmatrix}\n", " 0 & 5 \\\\\n", " 6 & 7 \\\\\n", " \\end{bmatrix}=\n", " \\begin{bmatrix}\n", " 1 \\cdot \\begin{bmatrix}\n", " 0 & 5 \\\\\n", " 6 & 7 \\\\\n", " \\end{bmatrix} & \n", " 2 \\cdot \\begin{bmatrix}\n", " 0 & 5 \\\\\n", " 6 & 7 \\\\\n", " \\end{bmatrix} \\\\\n", " 3 \\cdot \\begin{bmatrix}\n", " 0 & 5 \\\\\n", " 6 & 7 \\\\\n", " \\end{bmatrix} & \n", " 4 \\cdot \\begin{bmatrix}\n", " 0 & 5 \\\\\n", " 6 & 7 \\\\\n", " \\end{bmatrix} \\\\\n", " \\end{bmatrix}=\n", " \\begin{bmatrix}\n", " 1\\cdot 0 & 1\\cdot 5 & 2\\cdot 0 & 2\\cdot 5 \\\\\n", " 1\\cdot 6 & 1\\cdot 7 & 2\\cdot 6 & 2\\cdot 7 \\\\\n", " 3\\cdot 0 & 3\\cdot 5 & 4\\cdot 0 & 4\\cdot 5 \\\\\n", " 3\\cdot 6 & 3\\cdot 7 & 4\\cdot 6 & 4\\cdot 7 \\\\\n", " \\end{bmatrix}.\n", " \$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Back to our finite difference operators, on a 2D grid, we have the following\n", "\$$\n", "\\bf{D}_x^ + = \\left[ \\begin{array}{*{20}{c}}\n", "\\bf{D}^+ &{}&{}&{}&{}\\\\\n", "{}&\\bf{D}^+&{}&{}&{}\\\\\n", "{}&{}& \\ddots &{}&{}\\\\\n", "{}&{}&{}& \\ddots &{}\\\\\n", "{}&{}&{}&{}&\\bf{D}^+\n", "\\end{array} \\right] = \\bf{I}_y \\otimes \\bf{D}^+({N_y})\n", "\$$\n", "where $\\mathbf{I}_y$ is the identity matrix of size $N_y\\times N_y$ and $\\mathbf{D}^+$ is of size $N_x\\times N_x$. Similarly, we have\n", "\$$\n", "\\mathbf{D}_x^- = \\mathbf{I}_y\\otimes \\mathbf{D}^-(N_x)\n", "\$$\n", "The effect of the Kronecker product $\\mathbf{I}_y\\otimes \\mathbf{D}$ is to replicate $\\mathbf{D}$ by $N_y$ times." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The situation is a bit more different for the $y$-derivatives. In this case, we want to offset the off-diagonal components of $\\mathbf{D}$ by $N_x$, i.e. $(i+1, j) \\to (i, j+1)$. To do this, we have to right-multiply $\\mathbf{D}$ by $\\mathbf{I}_x$.\n", "\$$\n", "\\mathbf{D}_y^+ = \\mathbf{D}^+(N_y) \\otimes \\mathbf{I}_x\n", "\$$\n", "and\n", "\$$\n", "\\mathbf{D}_y^- = \\mathbf{D}^-(N_y) \\otimes \\mathbf{I}_x\n", "\$$\n", "where $\\mathbf{I}_x$ is the identity matrix of size $N_x\\times N_x$ and $\\mathbf{D}^{+,-}$ is of size $N_y\\times N_y$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Three Dimensions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In three dimensions, the operators can be constructed as follows\n", "\$$\n", "\\mathbf{D_x^{+,-}} = \\mathbf{I}_z \\otimes \\mathbf{I}_y \\otimes \\mathbf{D}^{+,-} \\\\\n", "\\mathbf{D_y^{+,-}} = \\mathbf{I}_z \\otimes \\mathbf{D}^{+,-} \\otimes \\mathbf{I}_x \\\\\n", "\\mathbf{D_z^{+,-}} = \\mathbf{D}^{+,-} \\otimes \\mathbf{I}_y \\otimes \\mathbf{I}_x \\\\ \n", "\$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Bottom Line**\n", "1. $\\mathbf{I}(N) \\otimes \\mathbf{B}(M)$ creates a block diagonal matrix of $\\mathbf{B}$'s\n", "2. $\\mathbf{B}(M) \\otimes \\mathbf{I}(N)$ offsets the off-diagonal terms in $\\mathbf{B}$ by $N$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementation\n", "We will implement the Kronecker product formulation in a single class called GridOps" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "from numpy import zeros, ones, eye, diag, kron\n", "\n", "class GridOps:\n", " '''\n", " Creates x, y, and z-direction 2D, or 3D versions of a 1D operator defined by Op1D.\n", " N : A list or array containing the grid dimensions, [Nx, Ny, Nz].\n", " Op1D: The name of a basic 1D operator. Op1D must be of the form Op1D(n,h) where n is a single valued integer\n", " designating the number of points in that one-dimension and h is the spacing.\n", " Δ : A list or array containing the grid spacing, [dx, dy, dz]. Defaults to [1,1,1]\n", " '''\n", " def __init__(self, Op1D, N, Δ=[1,1,1]):\n", " self.N = N\n", " self.Δ = Δ\n", " self.Op1D = Op1D\n", " \n", " def OpX(self):\n", " '''\n", " Creates x-direction 2D, or 3D versions of a 1D operator defined by Op1D.\n", " ''' \n", " N = self.N\n", " Δ = self.Δ\n", " Op = self.Op1D\n", " return kron(eye(N[2]), kron(eye(N[1]), Op (N[0],Δ[0]) ) )\n", " \n", " def OpY(self):\n", " '''\n", " Creates y-direction 2D, or 3D versions of a 1D operator defined by Op1D.\n", " '''\n", " N = self.N\n", " Δ = self.Δ\n", " Op = self.Op1D\n", " return kron( eye(N[2]), kron(Op(N[1],Δ[1]), eye(N[0]) ) ) \n", "\n", " def OpZ(self):\n", " '''\n", " Creates z-direction 2D, or 3D versions of a 1D operator defined by Op1D.\n", " ''' \n", " N = self.N\n", " Δ = self.Δ\n", " Op = self.Op1D \n", " return kron(Op(N[2],Δ[2]), kron(eye(N[1]), eye(N[0]) ) ) \n", " \n", " def Sum(self):\n", " '''\n", " Returns the sum of all three operators. Useful for returning a Laplacian for example.\n", " '''\n", " return self.OpX() + self.OpY() + self.OpZ()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Below are some example 1D finite difference operators" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [], "source": [ "def d_plus1d(n, h=1):\n", " '''\n", " Defines a basic forward difference operator in 1D (first derivative, first order)\n", " '''\n", " # periodic forward difference\n", " d = np.ones(n, dtype=int)\n", " ud = np.ones(n-1, dtype=int)\n", " D = diag(-d) + diag(ud,1)\n", " D[-1,0] = 1\n", " return D/h\n", "\n", "def d_minus1d(n, h=1):\n", " '''\n", " Defines a basic backward difference operator in 1D (first derivative, first order)\n", " '''\n", " return -d_plus1d(n,h).T\n", "\n", "def laplacian1d(n, h=1):\n", " '''\n", " Defines a basic 1D Laplacian operator (second derivative), cell centered, second order\n", " ''' \n", " result = 0 if n <= 1 else d_plus1d(n,h) @ d_minus1d(n,h)\n", " return result" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "from numpy import zeros, ones, eye, diag, kron\n", "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "%config InlineBackend.figure_format = 'svg'" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[-1. 1. 0. 0. 0.]\n", " [ 0. -1. 1. 0. 0.]\n", " [ 0. 0. -1. 1. 0.]\n", " [ 0. 0. 0. -1. 1.]\n", " [ 1. 0. 0. 0. -1.]]\n" ] } ], "source": [ "print(d_plus1d(5))" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[ 1. -0. -0. -0. -1.]\n", " [-1. 1. -0. -0. -0.]\n", " [-0. -1. 1. -0. -0.]\n", " [-0. -0. -1. 1. -0.]\n", " [-0. -0. -0. -1. 1.]]\n" ] } ], "source": [ "print(d_minus1d(5))" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[-2. 1. 0. 0. 1.]\n", " [ 1. -2. 1. 0. 0.]\n", " [ 0. 1. -2. 1. 0.]\n", " [ 0. 0. 1. -2. 1.]\n", " [ 1. 0. 0. 1. -2.]]\n" ] } ], "source": [ "print(laplacian1d(5))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Two Dimensional Example\n", "In what follows, we build a few 2D versions of the operators we defined above" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [], "source": [ "N = [3,3,1] # set grid size to 4x4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To define 2D versions of $\\mathbf{D}^{+,-}$ and the 1d Laplacian, we simply call the class GridOps" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [], "source": [ "Dplus2D = GridOps(d_plus1d, N)\n", "Dminus2D = GridOps(d_minus1d, N)\n", "Lap2D = GridOps(laplacian1d, N)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now visualize these operators by accessing the methods defined by GridOps. For example, The forward difference version of $\\partial/\\partial x$ on this 2D Grid is given calling OpX() on the corresponding GridOps" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[-1. 1. 0. -0. 0. 0. -0. 0. 0.]\n", " [ 0. -1. 1. 0. -0. 0. 0. -0. 0.]\n", " [ 1. 0. -1. 0. 0. -0. 0. 0. -0.]\n", " [-0. 0. 0. -1. 1. 0. -0. 0. 0.]\n", " [ 0. -0. 0. 0. -1. 1. 0. -0. 0.]\n", " [ 0. 0. -0. 1. 0. -1. 0. 0. -0.]\n", " [-0. 0. 0. -0. 0. 0. -1. 1. 0.]\n", " [ 0. -0. 0. 0. -0. 0. 0. -1. 1.]\n", " [ 0. 0. -0. 0. 0. -0. 1. 0. -1.]]\n" ] }, { "data": { "text/plain": [ "" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n" ], "text/plain": [ "