\n", "

"]}, {"cell_type": "markdown", "metadata": {}, "source": ["\n", "

\n", "\n", "

\n", " Computational Seismology

\n", " Discontinuous Galerkin Method - 1D Elastic Wave Equation, Homogeneous case

\n", " \n", "\n", "\n", "\n", "

\n", "\n", "\n", "---\n", "\n", "This notebook is part of the supplementary material \n", "to [Computational Seismology: A Practical Introduction](https://global.oup.com/academic/product/computational-seismology-9780198717416?cc=de&lang=en&#), \n", "Oxford University Press, 2016.\n", "\n", "\n", "##### Authors:\n", "* Stephanie Wollherr ([@swollherr](https://github.com/swollherr))\n", "* David Vargas ([@dvargas](https://github.com/davofis))\n", "* Heiner Igel ([@heinerigel](https://github.com/heinerigel))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Basic Equations\n", "\n", "The source-free elastic wave equation in 1D reads \n", "\n", "\\begin{align}\n", "\\partial_t \\sigma - \\mu \\partial_x v & = 0 \\\\ \n", "\\partial_t v - \\frac{1}{\\rho} \\partial_x \\sigma & = 0\n", "\\end{align}\n", "\n", "with $\\rho$ the density and $\\mu$ the shear modulus. This equation in matrix-vector notation follows\n", "\n", "\\begin{equation}\n", "\\partial_t \\mathbf{Q} + \\mathbf{A} \\partial_x \\mathbf{Q} = 0\n", "\\end{equation}\n", "\n", "where $\\mathbf{Q} = (\\sigma, v)$ is the vector of unknowns and the matrix $\\mathbf{A}$ contains the parameters $\\rho$ and $\\mu$. We seek to solve the linear advection equation as a hyperbolic equation $ \\partial_t u + \\mu \\ \\partial_x u=0$. A series of steps need to be done:\n", "\n", "1) The weak form of the equation is derived by multiplying both sides by an arbitrary test function. \n", "\n", "2) Apply the stress Free Boundary Condition after integration by parts\n", "\n", "3) We approximate the unknown field $\\mathbf{Q}(x,t)$ by a sum over space-dependent basis functions $\\ell_i$ weighted by time-dependent coefficients $\\mathbf{Q}(x_i,t)$, as we did in the spectral elements method. As interpolating functions we choose the Lagrange polynomials and use $\\xi$ as the space variable representing the elemental domain:\n", "\n", "\\begin{equation}\n", "\\mathbf{Q}(\\xi,t) \\ = \\ \\sum_{i=1}^{N_p} \\mathbf{Q}(\\xi_i,t) \\ell_i(\\xi) \\qquad with \\qquad \\ell_i^{(N)} (\\xi) \\ := \\ \\prod_{j = 1, \\ j \\neq i}^{N+1} \\frac{\\xi - \\xi_j}{\\xi_i-\\xi_j}, \\quad i,j = 1, 2, \\dotsc , N + 1 \n", "\\end{equation}\n", "\n", "4) The continuous weak form is written as a system of linear equations by considering the approximated displacement field. Finally, the semi-discrete scheme can be written in matrix-vector form as\n", "\n", "\\begin{equation}\n", "\\mathbf{M}\\partial_t \\mathbf{Q} = \\mathbf{A}\\mathbf{K}\\mathbf{Q} - \\mathbf{Flux}\n", "\\end{equation}\n", "\n", "5) Time extrapolation is done after applying a standard 1st order finite-difference approximation to the time derivative, we call it the Euler scheme.\n", "\n", "\\begin{equation}\n", "\\mathbf{Q}^{t+1} \\approx \\mathbf{Q}^{t} + dt\\mathbf{M}^{-1}(\\mathbf{A}\\mathbf{K}\\mathbf{Q} - \\mathbf{Flux})\n", "\\end{equation}\n", "\n", "This notebook implements both Euler and Runge-Kutta schemes for solving the free source version of the elastic wave equation in a homogeneous media. To keep the problem simple, we use as spatial initial condition a Gauss function with half-width $\\sigma$\n", "\n", "\\begin{equation}\n", "Q(x,t=0) = e^{-1/\\sigma^2 (x - x_{o})^2}\n", "\\end{equation}"]}, {"cell_type": "code", "execution_count": null, "metadata": {"code_folding": [0]}, "outputs": [], "source": ["# Import all necessary libraries, this is a configuration step for the exercise.\n", "# Please run it before the simulation code!\n", "import numpy as np\n", "import matplotlib\n", "# Show Plot in The Notebook\n", "matplotlib.use(\"nbagg\")\n", "import matplotlib.pyplot as plt\n", "\n", "from gll import gll\n", "from lagrange1st import lagrange1st\n", "from flux_homo import flux"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### 1. Initialization of setup"]}, {"cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": ["# Initialization of setup\n", "# --------------------------------------------------------------------------\n", "c = 2500 # acoustic velocity [m/s]\n", "tmax = 2.0 # Length of seismogram [s]\n", "xmax = 10000 # Length of domain [m]\n", "vs = 2500 # Advection velocity \n", "rho = 2500 # Density [kg/m^3]\n", "mu = rho*vs**2 # shear modulus\n", "N = 4 # Order of Lagrange polynomials\n", "ne = 200 # Number of elements\n", "sig = 200 # Gaussian width\n", "x0 = 5000 # x location of Gaussian \n", "eps = 0.4 # Courant criterion\n", "iplot = 20 # Plotting frequency \n", "imethod = 'RK' # 'Euler', 'RK'\n", "#--------------------------------------------------------------------\n", "\n", "# GLL points and integration weights\n", "[xi,w] = gll(N) # xi, N+1 coordinates [-1 1] of GLL points\n", " # w Integration weights at GLL locations\n", "# Space domain\n", "le = xmax/ne # Length of elements\n", "ng = ne*N + 1\n", "\n", "# Vector with GLL points \n", "k=0\n", "xg = np.zeros((N+1)*ne)\n", "for i in range(0, ne):\n", " for j in range(0, N+1):\n", " k += 1\n", " xg[k-1] = i*le + .5*(xi[j]+1)*le\n", " \n", "x = np.reshape(xg, (N+1, ne), order='F').T\n", "\n", "# Calculation of time step acoording to Courant criterion\n", "dxmin = np.min(np.diff(xg[1:N+1]))\n", "dt = eps*dxmin/vs # Global time step\n", "nt = int(np.floor(tmax/dt))\n", "\n", "# Mapping - Jacobian\n", "J = le/2 # Jacobian\n", "Ji = 1/J # Inverse Jacobian\n", "\n", "# 1st derivative of Lagrange polynomials\n", "l1d = lagrange1st(N) "]}, {"cell_type": "markdown", "metadata": {"solution2": "hidden", "solution2_first": true}, "source": ["### 2. Elemental Mass and Stiffness matrices\n", "\n", "The mass and the stiffness matrix are calculated prior time extrapolation, so they are pre-calculated and stored at the beginning of the code. \n", "\n", "The integrals defined in the mass and stiffness matrices are computed using a numerical quadrature, in this cases the GLL quadrature that uses the GLL points and their corresponding weights to approximate the integrals. Hence,\n", "\n", "\\begin{equation}\n", "M_{ij}^k=\\int_{-1}^1 \\ell_i^k(\\xi) \\ell_j^k(\\xi) \\ J \\ d\\xi = \\sum_{m=1}^{N_p} w_m \\ \\ell_i^k (x_m) \\ell_j^k(x_m)\\ J =\\sum_{m=1}^{N_p} w_m \\delta_{im}\\ \\delta_{jm} \\ J= \\begin{cases} w_i \\ J \\ \\ \\text{ if } i=j \\\\ 0 \\ \\ \\ \\ \\ \\ \\ \\text{ if } i \\neq j\\end{cases}\n", "\\end{equation}\n", "\n", "that is a **diagonal mass matrix!**. Subsequently, the stiffness matrices is given as \n", " \n", "\\begin{equation} \n", "K_{i,j}= \\int_{-1}^1 \\ell_i^k(\\xi) \\cdot \\partial _x \\ell_j^k(\\xi) \\ d\\xi= \\sum_{m=1}^{N_p} w_m \\ \\ell_i^k(x_m)\\cdot \\partial_x \\ell_j^k(x_m)= \\sum_{m=1}^{N_p} w_m \\delta_{im}\\cdot \\partial_x\\ell_j^k(x_m)= w_i \\cdot \\partial_x \\ell_j^k(x_i) \n", "\\end{equation}\n", "\n", "The Lagrange polynomials and their properties have been already used, they determine the integration weights $w_i$ that are returned by the python method \"gll\". Additionally, the fist derivatives of such basis, $\\partial_x \\ell_j^k(x_i)$, are needed, the python method \"Lagrange1st\" returns them.\n", "\n", "#### Exercise 1 \n", "Now we have all the ingredients to calculate the mass and stiffness matrix, initialize these matrices in the following cell. Compute the inverse mass matrix, keep in mind that it is diagonal."]}, {"cell_type": "code", "execution_count": null, "metadata": {"lines_to_next_cell": 2, "tags": ["exercise"]}, "outputs": [], "source": ["#################################################################\n", "# IMPLEMENT THE ELEMENTAL MASS MATRIX HERE!\n", "#################################################################\n", "\n", "\n", "#################################################################\n", "# COMPUTE THE INVERSE MASS MATRIX HERE!\n", "#################################################################\n", "\n", "\n", "#################################################################\n", "# IMPLEMENT THE ELEMENTAL STIFFNESS MATRIX HERE!\n", "#################################################################"]}, {"cell_type": "code", "execution_count": null, "metadata": {"solution2": "hidden", "tags": ["solution"]}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {"solution2": "hidden", "solution2_first": true}, "source": ["### 3. Flux Matrices\n", "\n", "As in the case of finite volumes when we solve the 1D elastic wave equation for an homogeneous media, we assume the coefficients of matrix A to be constant inside the element.\n", "\n", "\\begin{equation} \n", "\\mathbf{A}=\n", " \\begin{pmatrix}\n", " 0 & -\\mu \\\\\n", " -1/\\rho & 0 \n", " \\end{pmatrix}\n", "\\end{equation}\n", "\n", "Now we need to diagonalize $\\mathbf{A}$. Introducing the seismic impedance $Z = \\rho c$ with $c = \\sqrt{\\mu/\\rho}$, we have\n", " \n", "\\begin{equation}\n", "\\mathbf{A} = \\mathbf{R}^{-1}\\mathbf{\\Lambda}\\mathbf{R}\n", "\\qquad\\text{,}\\qquad\n", "\\mathbf{\\Lambda}=\n", " \\begin{pmatrix}\n", " -c & 0 \\\\\n", " 0 & c \n", " \\end{pmatrix}\n", "\\qquad\\text{,}\\qquad\n", "\\mathbf{R} = \n", " \\begin{pmatrix}\n", " Z & -Z \\\\\n", " 1 & 1 \n", " \\end{pmatrix}\n", "\\qquad\\text{and}\\qquad\n", "\\mathbf{R}^{-1} = \\frac{1}{2Z}\n", " \\begin{pmatrix}\n", " 1 & Z \\\\\n", " -1 & Z \n", " \\end{pmatrix}\n", "\\end{equation}\n", "\n", "We decompose the solution into right propagating $\\mathbf{\\Lambda}^{+}$ and left propagating eigenvalues $\\mathbf{\\Lambda}^{-}$ where\n", "\n", "\\begin{equation}\n", "\\mathbf{\\Lambda}^{+}=\n", " \\begin{pmatrix}\n", " -c & 0 \\\\\n", " 0 & 0 \n", " \\end{pmatrix}\n", "\\qquad\\text{,}\\qquad\n", "\\mathbf{\\Lambda}^{-}=\n", " \\begin{pmatrix}\n", " 0 & 0 \\\\\n", " 0 & c \n", " \\end{pmatrix}\n", "\\qquad\\text{and}\\qquad\n", "\\mathbf{A}^{\\pm} = \\mathbf{R}^{-1}\\mathbf{\\Lambda}^{\\pm}\\mathbf{R}\n", "\\end{equation}\n", "\n", "This strategy allows us to formulate the Flux term in the discontinuous Galerkin method.\n", "\n", "#### Exercise 2\n", "Initialize all relevant matrices, i.e $R$, $R^{-1}$, $\\mathbf{\\Lambda}^{+}$, $\\mathbf{\\Lambda}^{-}$, $\\mathbf{A}^{+}$, $\\mathbf{A}^{-}$, $\\mathbf{A}$."]}, {"cell_type": "code", "execution_count": null, "metadata": {"tags": ["exercise"]}, "outputs": [], "source": ["#################################################################\n", "# INITIALIZE ALL MATRICES HERE!\n", "#################################################################\n", "# Z = \n", "# R = \n", "# Rinv = \n", "\n", "# Lm = \n", "# Lp = \n", "\n", "# Ap = \n", "# Am = \n", "\n", "# A = "]}, {"cell_type": "code", "execution_count": null, "metadata": {"solution2": "hidden", "tags": ["solution"]}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### 4. Discontinuous Galerkin Solution\n", "\n", "The principal characteristic of the discontinuous Galerkin Method is the communication between the element neighbors using a flux term, in general it is given \n", "\n", "\\begin{equation}\n", "\\mathbf{Flux} = \\int_{\\partial D_k} \\mathbf{A}\\mathbf{Q}\\ell_j(\\xi)\\mathbf{n}d\\xi\n", "\\end{equation}\n", "\n", "this term leads to four flux contributions for left and right sides of the elements\n", "\n", "\\begin{equation}\n", "\\mathbf{Flux} = -\\mathbf{A}_{k}^{-}\\mathbf{Q}_{l}^{k}\\mathbf{F}^{l} + \\mathbf{A}_{k}^{+}\\mathbf{Q}_{r}^{k}\\mathbf{F}^{r} - \\mathbf{A}_{k}^{+}\\mathbf{Q}_{r}^{k-1}\\mathbf{F}^{l} + \\mathbf{A}_{k}^{-}\\mathbf{Q}_{l}^{k+1}\\mathbf{F}^{r}\n", "\\end{equation}\n", "\n", "\n", "\n", "Last but not least, we have to solve our semi-discrete scheme that we derived above using an appropriate time extrapolation, in the code below we implemented two different time extrapolation schemes:\n", "\n", "1) **Euler scheme** \n", "\n", "\\begin{equation}\n", "\\mathbf{Q}^{t+1} \\approx \\mathbf{Q}^{t} + dt\\mathbf{M}^{-1}(\\mathbf{A}\\mathbf{K}\\mathbf{Q} - \\mathbf{Flux})\n", "\\end{equation}\n", "\n", "2) Second-order **Runge-Kutta method** (also called predictor-corrector scheme) \n", "\n", "\\begin{eqnarray*} \n", "k_1 &=& f(t_i, y_i) \\\\\n", "k_2 &=& f(t_i + dt, y_i + dt k_1) \\\\\n", "& & \\\\\n", "y_{i+1} &=& y_i + \\frac{dt}{2} (k_1 + k_2)\n", "\\end{eqnarray*}\n", "\n", "with $f$ that corresponds with $\\mathbf{M}^{-1}(\\mathbf{A}\\mathbf{K}\\mathbf{Q} - \\mathbf{Flux})$\n", "\n", "#### Exercise 3\n", "In order to validate our numerical solution, we ask to compare with the corresponding analytical solution as we did in the finite volumes implementation. Implement the analytical solution for the 1D elastic wave equation in homogeneous media and plot it together with the discontinuous Galerkin numerical solution."]}, {"cell_type": "code", "execution_count": null, "metadata": {"tags": ["exercise"]}, "outputs": [], "source": ["# DG Solution, Time extrapolation\n", "# ---------------------------------------------------------------\n", "\n", "# Initalize solution vectors\n", "Q = np.zeros([ne, N+1, 2])\n", "Qnew = np.zeros([ne, N+1, 2])\n", "\n", "k1 = np.zeros([ne, N+1, 2])\n", "k2 = np.zeros([ne, N+1, 2])\n", "\n", "Q[:,:,0] = np.exp(-1/sig**2*((x-x0))**2)\n", "Qs = np.zeros(xg.size) # for plotting\n", "Qv = np.zeros(xg.size) # for plotting \n", "Qa = np.zeros((2, xg.size)) # for analytical solution\n", "\n", "# Initialize animated plot\n", "# ---------------------------------------------------------------\n", "fig = plt.figure(figsize=(10,6))\n", "ax1 = fig.add_subplot(2,1,1)\n", "ax2 = fig.add_subplot(2,1,2)\n", "line1 = ax1.plot(xg, Qs, 'k', xg, Qa[0,:], 'r--', lw=1.5)\n", "line2 = ax2.plot(xg, Qv, 'k', xg, Qa[1,:], 'r--', lw=1.5) \n", "ax1.set_ylabel('Stress')\n", "ax2.set_ylabel('Velocity')\n", "ax2.set_xlabel(' x ')\n", "plt.suptitle('Homogeneous Disc. Galerkin - %s method'%imethod, size=16)\n", "\n", "plt.ion() # set interective mode\n", "plt.show()\n", "\n", "# ---------------------------------------------------------------\n", "# Time extrapolation\n", "# ---------------------------------------------------------------\n", "for it in range(nt): \n", " if imethod == 'Euler': # Euler \n", " # Calculate Fluxes \n", " Flux = flux(Q, N, ne, Ap, Am) \n", " # Extrapolate each element using flux F \n", " for i in range(1,ne-1):\n", " Qnew[i,:,0] = dt * Minv @ (-mu * K @ Q[i,:,1].T - Flux[i,:,0].T) + Q[i,:,0].T\n", " Qnew[i,:,1] = dt * Minv @ (-1/rho * K @ Q[i,:,0].T - Flux[i,:,1].T) + Q[i,:,1].T \n", "\n", " elif imethod == 'RK': \n", " # Calculate Fluxes\n", " Flux = flux(Q, N, ne, Ap, Am)\n", " # Extrapolate each element using flux F \n", " for i in range(1,ne-1):\n", " k1[i,:,0] = Minv @ (-mu * K @ Q[i,:,1].T - Flux[i,:,0].T)\n", " k1[i,:,1] = Minv @ (-1/rho * K @ Q[i,:,0].T - Flux[i,:,1].T) \n", "\n", " for i in range(1,ne-1):\n", " Qnew[i,:,0] = dt * Minv @ (-mu * K @ Q[i,:,1].T - Flux[i,:,0].T) + Q[i,:,0].T \n", " Qnew[i,:,1] = dt * Minv @ (-1/rho * K @ Q[i,:,0].T - Flux[i,:,1].T) + Q[i,:,1].T \n", "\n", " Flux = flux(Qnew,N,ne,Ap,Am)\n", "\n", " for i in range(1,ne-1):\n", " k2[i,:,0] = Minv @ (-mu * K @ Qnew[i,:,1].T - Flux[i,:,0].T)\n", " k2[i,:,1] = Minv @ (-1/rho * K @ Qnew[i,:,0].T - Flux[i,:,1].T) \n", " \n", " # Extrapolate \n", " Qnew = Q + (dt/2) * (k1 + k2)\n", " else:\n", " raise NotImplementedError\n", "\n", " Q, Qnew = Qnew, Q\n", "\n", " # -------------------------------------- \n", " # Animation plot. Display solution \n", " if not it % iplot: \n", " for l in line1:\n", " l.remove()\n", " del l \n", " for l in line2:\n", " l.remove()\n", " del l \n", "\n", " # stretch for plotting\n", " k = 0\n", " for i in range(ne):\n", " for j in range(N+1):\n", " Qs[k] = Q[i,j,0]\n", " Qv[k] = Q[i,j,1] \n", " k = k + 1\n", " \n", " #################################################################\n", " # IMPLEMENT THE ANALYTICAL SOLUTION HERE!\n", " #################################################################\n", " \n", " # -------------------------------------- \n", " # Display lines\n", " line1 = ax1.plot(xg, Qs, 'k', xg, Qa[0,:], 'r--', lw=1.5)\n", " line2 = ax2.plot(xg, Qv, 'k', xg, Qa[1,:], 'r--', lw=1.5)\n", " plt.legend(iter(line2), ('D. Galerkin', 'Analytic'))\n", " plt.gcf().canvas.draw()"]}, {"cell_type": "markdown", "metadata": {"tags": ["solution"]}, "source": []}, {"cell_type": "code", "execution_count": null, "metadata": {"code_folding": [70], "tags": ["solution"]}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}}, "nbformat": 4, "nbformat_minor": 2}