12_mixed.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "<table>\n",
    " <tr align=left><td><img align=left src=\"https://i.creativecommons.org/l/by/4.0/88x31.png\">\n",
    " <td>Text provided under a Creative Commons Attribution license, CC-BY. All code is made available under the FSF-approved MIT license. (c) Kyle T. Mandli</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Mixed Equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We now explore how we might use the methods we have analyzed and developed to solve more complex equations that do not easily fall into one of the classifications for PDEs we have studied."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We will focus here on PDEs of the form\n",
    "$$\n",
    "    u_t = \\mathcal{A}_1(u) + \\mathcal{A}_2(u) + \\cdots + \\mathcal{A}_N(u)\n",
    "$$\n",
    "where the $\\mathcal{A}_j(u)$ are functions of $u$ and its derivatives (also possibly non-linear)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since most of the methods we will discuss can be generalized from the case of only two operators $\\mathcal{A}_j$ we will focus our attention on the PDE\n",
    "$$\n",
    "    u_t = \\mathcal{A}(u) + \\mathcal{B}(u).\n",
    "$$\n",
    "Let's now consider some examples of these types of equations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example - Multidimensional Problems\n",
    "\n",
    "We saw already how we might approach multi-dimensional problems coupled with a time derivative.  These also are considered mixed and many of the methods we will consider are applicable to multidimensional problems such as the heat equation\n",
    "$$\n",
    "    u_t = \\kappa(u_{xx} + u_{yy})\n",
    "$$\n",
    "or a multidimensional hyperbolic PDE\n",
    "$$\n",
    "    u_t + f(u)_x + g(u)_y = 0.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example - Reaction-Diffusion Equations\n",
    "\n",
    "We can add another term to the heat equation which often represents a chemical reaction term (also sometimes called a source or sync term) so that we have\n",
    "$$\n",
    "    u_t = \\kappa u_{xx} + R(u).\n",
    "$$\n",
    "We may want to handle the term $R(u)$ differently than the diffusion term in case it has different temporal scales, maybe is not stiff, or is difficult to solve coupled to our approach to the heat equation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example - Advection-Diffusion Equations\n",
    "\n",
    "We have also seen cases when considering numerical methods for advection that the modified equations can represent advection-diffusion systems of the form\n",
    "$$\n",
    "    u_t + a u_x = \\kappa u_{xx}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "It turns out these types of equations are much more prevalent than just this, in fact the Navier-Stokes equations are an example of a set of constrained advection-diffusion equations (constrained due to incompressibility).  We also find nonlinear hyperbolic equations with viscous terms such as\n",
    "$$\n",
    "    u_t + f(u)_x = \\kappa u_{xx}\n",
    "$$\n",
    "to be common when approximating fluid dynamics in general.  The viscous Burgers equation\n",
    "$$\n",
    "    u_t + u u_x = \\epsilon u_{xx}\n",
    "$$\n",
    "is another example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example - Advection-Diffusion-Reaction Equations\n",
    "\n",
    "Why not combine all of the above?\n",
    "$$\n",
    "    u_t + f(u)_x = \\kappa u_{xx} + R(u)\n",
    "$$\n",
    "These types of equations are common in cases of reactive fluid flow.  Modeling combustion for instance usually involves 10-100 different reaction terms with widely disparate time scales making these very difficult problems to solve."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example - Advection-Dispersion\n",
    "\n",
    "We also saw modified equations in our study of hyperbolic PDEs that contained both advective and dispersive terms.  Another example of this type of equation is the Kortweg-de Vries (KdV) equation\n",
    "$$\n",
    "    u_t + u u_x = \\nu u_{xxx}.\n",
    "$$\n",
    "This equation can be derived from the Euler equations modeling incompressible fluid flow and represent a number of interesting phenomena, most notably soliton waves.  A similar equation is the nonlinear Schrödinger equation\n",
    "$$\n",
    "    i \\Psi_t(x,t) = -\\Psi_{xx}(x,t) + V(\\Psi)\n",
    "$$\n",
    "where $V(\\Psi)$ is a nonlinear potential."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Example - Advection-Diffusion-Dispersion-Hyperdiffusion-...\n",
    "\n",
    "The Kuramoto-Sivashinsky equation\n",
    "$$\n",
    "    u_t + \\frac{1}{2} (u_x)^2 = -u_{xx} - u_{xxxx}\n",
    "$$\n",
    "is another equation of interest.  It would appear to be ill-posed and maybe even blow up due to the signs in front of the diffusion but it turns out this is not the case and appropriate damping is supplied by the transport term (the right hand-side) to stabilize the equation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Fully Coupled Method of Lines\n",
    "\n",
    "The first approach we will study is one that we have introduced before.  We assume that some spatial discretization is fully applied to all the spatial terms leading to a system of equations of the form\n",
    "$$\n",
    "    U'(t) = F(U(t)).\n",
    "$$\n",
    "This approach can work and provides a lot of flexibility in terms of the order of accuracy and the stencils available but can run into problems when some terms on the right are stiff while others are not.  The best example of this is the advection-diffusion equation unless the relative strength of the advection vs. the diffusion (called the Peclet number) highly favors one term or the other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Fully Coupled Taylor Series Methods\n",
    "\n",
    "We can also utilize Taylor series to construct methods for mixed equations.  Consider the Taylor expansion in time\n",
    "$$\n",
    "    u(x, t + \\Delta t) \\approx u(x, t) + \\Delta t u_t + \\cdots,\n",
    "$$\n",
    "if we replace $u_t$ with the right hand side we create the method\n",
    "$$\n",
    "    U^{n+1}_j = U^n_j + \\Delta t (A(U^n_j)) + B(U^n_j))\n",
    "$$\n",
    "where $A$ and $B$ are appropriately discretized versions of $\\mathcal{A}$ and $\\mathcal{B}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can extend this to higher order by retaining more terms in the Taylor expansion.  Consider the two-dimensional hyperbolic PDE\n",
    "$$\n",
    "    u_t + a u_x + b u_y = 0.\n",
    "$$\n",
    "The truncated Taylor series to second order is\n",
    "$$\n",
    "    u(x, t + \\Delta t) \\approx u(x, t) + \\Delta t u_t + \\frac{\\Delta t^2}{2} u_{tt} + \\cdots,\n",
    "$$\n",
    "so we need to compute the $u_{tt}$ term.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Taking the derivative of the original equation we have\n",
    "$$\\begin{aligned}\n",
    "    u_{tt} &= -a u_{xt} - b u_{yt} \\\\\n",
    "    &= -a (u_t)_x - b (u_t)_y \\\\\n",
    "    &= -a (-a u_x - b u_y)_x - b (-a u_x - b u_y)_y \\\\\n",
    "    &= a^2 u_{xx} + a b u_{yx} + a b u_{xy} + b^2 u_{yy} \\\\\n",
    "    &= a^2 u_{xx} + 2 a b u_{xy} + b^2 u_{yy}.\n",
    "\\end{aligned}$$\n",
    "If these were systems of hyperbolic PDEs $a$ and $b$ would be matrices and we would have the slightly different expression\n",
    "$$\n",
    "    u_{tt} = A^2 u_{xx} + (A B + B A) u_{xy} + B^2 u_{yy}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This leads to the method\n",
    "$$\n",
    "    U^{n+1}_{ij} = U^n_{ij} - \\Delta t (A D_{x} U^n_{ij} + B D_{y} U^n_{ij}) + \\frac{1}{2} \\Delta t^2 (A^2 D^2_x U^n_{ij} + (A B + B A) D_x D_y U^n_{ij} + B^2 D^2_y U^n_{ij} )\n",
    "$$\n",
    "which is the two-dimensional Lax-Wendroff method if centered approximations are used to discretize the derivatives appropriately."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Fractional Step Methods\n",
    "\n",
    "One of the most common ways to deal with mixed equations is through a fractional step method (a.k.a. time-split, split-step, or operator splitting methods).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In essence we split up the problem into two steps, one that solves the terms dealing with $\\mathcal{A}$ and another that deals with $\\mathcal{B}$:\n",
    "$$\n",
    "    U^\\ast = \\mathcal{N}_A(U^n, \\Delta t) \\\\\n",
    "    U^{n+1} = \\mathcal{N}_B(U^\\ast, \\Delta t)\n",
    "$$\n",
    "where $\\mathcal{N}_{A}$ and $\\mathcal{N}_{B}$ represent one-step numerical methods for solving\n",
    "$$\n",
    "    u_t = \\mathcal{A}(u)\n",
    "$$\n",
    "and\n",
    "$$\n",
    "    u_t = \\mathcal{B}(u)\n",
    "$$\n",
    "respectively.  This first order accurate scheme is called *Godunov splitting*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This approach has the advantage of being able to use whatever method is appropriate for each of the operators $\\mathcal{A}$ and $\\mathcal{B}$, say an explicit and an implicit method for instance.  As presented above however this splitting is only 1st order accurate though is convergent as $\\Delta t \\rightarrow 0$ as long as the constituent methods are convergent on their individual problems.  In practice the \"splitting\" error is small compared to the time and space direct discretizations and this approach works well."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Multidimensional problems also can use fractional step splitting as we saw earlier.  In this context it is usually called *dimensional splitting* and can be very effective over a fully multi-dimensional approach, especially for higher dimensions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Error Analysis\n",
    "\n",
    "Let's now explore what kind of error is introduced due to our splitting error.  Consider the simple ODE\n",
    "$$\n",
    "    u_t = A u + B u\n",
    "$$\n",
    "where $A$ and $B$ are matrices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since we know the solution of this ODE we can single out the error produced by the splitting alone.  Take the methods $\\mathcal{N}$ and set them to the exact solution of the split equations so that\n",
    "$$\n",
    "    \\mathcal{N}_A(U, \\Delta t) = e^{A \\Delta t} U\n",
    "$$\n",
    "and\n",
    "$$\n",
    "    \\mathcal{N}_B(U, \\Delta t) = e^{B \\Delta t} U.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The fractional step approach will lead to the solution\n",
    "$$\\begin{aligned}\n",
    "    U^\\ast &= e^{A \\Delta t} U^{n} \\Rightarrow \\\\\n",
    "    U^{n+1} &= e^{B\\Delta t} U^\\ast = e^{B\\Delta t} e^{A \\Delta t} U^{n}.\n",
    "\\end{aligned}$$\n",
    "In essense $e^{B\\Delta t} e^{A \\Delta t}$ maps the initial condition at $t_n$ to the new time $t_{n+1}$ (called a solution operator)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The exact solution to the original ODE is also\n",
    "$$\n",
    "    u(t_n + \\Delta t) = e^{(A + B) \\Delta t} u(t_n)\n",
    "$$\n",
    "demonstrating that there is a difference in the approaches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Taylor expanding the matrix exponentials of the exact solution (the solution operator) we see that we should have\n",
    "$$\n",
    "    e^{(A + B) \\Delta t} = I + \\Delta t (A + B) + \\frac{\\Delta t^2}{2} (A+B)^2 + \\cdots\n",
    "$$\n",
    "while Taylor expanding the matrix exponentials in the fractional step approach leads to\n",
    "$$\\begin{aligned}\n",
    "    e^{B\\Delta t} e^{A \\Delta t} &= \\left (I + \\Delta t B + \\frac{\\Delta t^2}{2} B^2 + \\cdots \\right ) \\left (I + \\Delta t A + \\frac{\\Delta t^2}{2} A^2 + \\cdots \\right ) \\\\\n",
    "    &= I + \\Delta t (A + B) + \\frac{\\Delta t^2}{2} (A^2 + 2 B A + B^2) + \\cdots.\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Comparing the two expressions we see that the series are equivalent to the $\\mathcal{O}(\\Delta t^2)$ where the true solution has\n",
    "$$\n",
    "    (A + B)^2 = A^2 + A B + B A + B^2\n",
    "$$\n",
    "where as the approximation is\n",
    "$$\n",
    "    A^2 + 2 B A + B^2.\n",
    "$$\n",
    "Consequently subtracting the two expressions to find the error leaves us with \n",
    "$$\n",
    "    e^{(A + B) \\Delta t} - e^{B \\Delta t} e^{A \\Delta t} = \\tau^n = \\frac{\\Delta t^2}{2} (A B - B A)  + \\mathcal{O}(\\Delta t^3).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This term in the middle is often called the commutator of the operators $A$ and $B$ denoted by $[A, B] = A B - B A$.  If the commutator is 0 then the splitting is higher order accurate!  Note that this is true always when solving a scalar equation, in this case the entire Taylor series are identical and we find that there is no error introduced by the splitting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also formulate a second order method called *Strang splitting* which uses\n",
    "$$\n",
    "    U^\\ast = \\mathcal{A}(U^n, \\Delta t / 2) \\\\\n",
    "    U^{\\ast\\ast} = \\mathcal{B}(U^\\ast, \\Delta t) \\\\\n",
    "    U^{n+1} = \\mathcal{A}(U^{\\ast\\ast}, \\Delta t / 2).\n",
    "$$\n",
    "Following the analysis above the solution operator is\n",
    "$$\n",
    "    e^{A \\Delta t / 2} e^{B \\Delta t} e^{A \\Delta t /2}\n",
    "$$\n",
    "which agrees with the exact Taylor series regardless of the Taylor series up to third order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This may seem like a lot of work but in practice if we are taking two steps we can combine two evaluations of the individual methods to show that except for the first step we can simply alternate steps on the numerical method:\n",
    "$$\\begin{aligned}\n",
    "    U^{n+3} &= \\left (e^{A \\Delta t / 2} e^{B \\Delta t} e^{A \\Delta t /2} \\right)\\left (e^{A \\Delta t / 2} e^{B \\Delta t} e^{A \\Delta t /2} \\right)\\left (e^{A \\Delta t / 2} e^{B \\Delta t} e^{A \\Delta t /2} \\right) U^{n} \\\\\n",
    "    &= e^{A \\Delta t / 2} e^{B \\Delta t} e^{A \\Delta t} e^{B \\Delta t} e^{A \\Delta t} e^{B \\Delta t} e^{A \\Delta t /2}  U^{n}\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In terms of the multi-dimensional approach to the heat equation we discussed which has the form of Godunov splitting we saw that it was actually second order accurate.  Just to refresh the equation is\n",
    "$$\n",
    "    u_t = u_{xx} + u_{yy}\n",
    "$$\n",
    "with $\\mathcal{A} = u_{xx}$ and $\\mathcal{B} = u_{yy}$.  Since these operators commute with each other we see second order accurate approximations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Consider instead though what would happen if we have a spatial varying diffusion constant such that\n",
    "$$\n",
    "    u_t = (\\kappa(x,y)u_x)_x + (\\kappa(x,y)u_y)_y\n",
    "$$\n",
    "so that $\\mathcal{A} = (\\kappa(x,y)u_x)_x$ and $\\mathcal{B} = (\\kappa(x,y)u_y)_y$.  These no longer commute and the method as formulated is only formally first order accurate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One final caveat to fractional splitting is that the boundary conditions can be non-trivial to implement.  This arises due to the need for specifying a boundary condition at the intermediate stages and in general can be an issue in general if there are any time-dependent factors in the equation as what time to evaluate these functions at for the intermediate stages is not obvious."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Solve the advection-diffusion equation u_t + u_x = u_{xx}\n",
    "import scipy.sparse as sparse\n",
    "import scipy.sparse.linalg as linalg\n",
    "\n",
    "def CN_step(delta_x, delta_t, t_0, U_0, g_0, g_1, kappa=1.0):\n",
    "    \"\"\"Solve the heat equation u_t = \\kappa u_{xx}\"\"\"\n",
    "    \n",
    "    # Build solving matrix\n",
    "    r = numpy.ones(m) * delta_t / (2.0 * delta_x**2)\n",
    "    A = sparse.spdiags([-r, 1.0 + 2.0 * r, -r], [-1, 0, 1], m, m).tocsr()\n",
    "    \n",
    "    # Build matrix for the right hand side computation\n",
    "    B = sparse.spdiags([r, 1.0 - 2.0 * r, r], [-1, 0, 1],  m, m).tocsr()\n",
    "    \n",
    "    # Construct right-hand side\n",
    "    b = B.dot(U_0)\n",
    "    b[0] += delta_t / (2.0 * delta_x**2) * (g_0(t_0) + g_0(t_0 + delta_t))\n",
    "    b[-1] += delta_t / (2.0 * delta_x**2) * (g_1(t_0) + g_1(t_0 + delta_t))\n",
    "    \n",
    "    # Solve system\n",
    "    return linalg.spsolve(A, b)\n",
    "\n",
    "def LW_step(delta_x, delta_t, t_0, U_0, g_0, g_1, a=1.0):\n",
    "    \"\"\"Solve the advection equation u_t + a u_x = 0\"\"\"\n",
    "    u_true = lambda x, t: numpy.exp(-20.0 * ((x - t) - 2.0)**2) + numpy.exp(-((x - t) - 5.0)**2)\n",
    "\n",
    "    U = numpy.empty(U_0.shape)\n",
    "    \n",
    "    U[0] = U_0[0] - delta_t / (2.0 * delta_x) * (U_0[1] - U_0[-1]) \\\n",
    "                    + delta_t**2 / (2.0 * delta_x**2) * (U_0[1] - 2.0 * U_0[0] + U_0[-1])\n",
    "    U[1:-1] = U_0[1:-1] - delta_t / (2.0 * delta_x) * (U_0[2:] - U_0[:-2]) \\\n",
    "                          + delta_t**2 / (2.0 * delta_x**2) * (U_0[2:] - 2.0 * U_0[1:-1] + U_0[:-2])\n",
    "    U[-1] = U_0[-1] - delta_t / (2.0 * delta_x) * (U_0[0] - U_0[-2]) \\\n",
    "                      + delta_t**2 / (2.0 * delta_x**2) * (U_0[0] - 2.0 * U_0[-1] + U_0[-2])\n",
    "    \n",
    "    return U\n",
    "\n",
    "# Problem specification\n",
    "L = 1.0\n",
    "g_0 = None\n",
    "g_1 = None\n",
    "\n",
    "# Spatial discretization\n",
    "m = 100\n",
    "x = numpy.linspace(0.0, L, m)\n",
    "delta_x = L / (m + 1.0)\n",
    "    \n",
    "# Time discretization\n",
    "delta_t = C * delta_x\n",
    "t = numpy.arange(0.0, 1.0, delta_t)\n",
    "N = len(t)\n",
    "cfl = 0.8\n",
    "delta_t = cfl * delta_x\n",
    "\n",
    "# Godunov operator-splitting\n",
    "for n in xrange(N):\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Implicit-Explicit (IMEX) Methods \n",
    "\n",
    "Suppose that one of our operators $\\mathcal{A}(u)$ represents stiff terms that we really would rather integrate using an implicit method while $\\mathcal{B}(u)$ is non-stiff and we would like to apply an explicit method.  Instead of employing a fractional step method we can an *implicit-explicit* (IMEX) method.  These have the advantage that they are fully coupled (hence no splitting error) and are designed to be able to choose which terms to treat explicitly and which implicitly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One simple example of this is combining backward and forward Euler, evaluating the non-stiff terms at $U^n$ and the stiff terms at $U^{n+1}$ to find\n",
    "$$\n",
    "    U^{n+1} = U^n + \\Delta t (\\mathcal{A}(U^{n+1}) + \\mathcal{B}(U^n)).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Another example that is second-order using Adams-Bashforth for the explicit component and the trapezoidal rule for the implicit leads to\n",
    "$$\n",
    "    U^{n+1} = U^n + \\frac{\\Delta t}{2} \\left(\\mathcal{A}(U^n) + \\mathcal{A}(U^{n+1}) + 3 \\mathcal{B}(U^n) - \\mathcal{B}(U^{n-1}) \\right ).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In general we can combine many of the methods we have studied to form these types of methods including both multi-step methods like the previous example and Runge-Kutta like, multi-stage methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exponential Time Differencing Methods\n",
    "\n",
    "For the final method we will look at consider the general nonlinear ODE\n",
    "$$\n",
    "    u' = f(u)\n",
    "$$\n",
    "and over the time interval $t \\in [t_n, t_{n+1}]$ we write this ODE as\n",
    "$$\n",
    "    u'(t) = A_n u(t) + \\mathcal{B}_n(u(t))\n",
    "$$\n",
    "where our notation suggests that $A_n$ is a matrix and therefore the first term is linear while the second term may not be and in general contains the nonlinearities from the original ODE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The basic idea of *exponential time differencing* (ETD) methods is to apply exact solution techniques (such as Duhamel's principle) to handle the linear part and a numerical method for the nonlinear part.  It is often common to let the linear part contain the stiff components of the equation (such as if we discretized a diffusion operator) and then use an explicit method to handle $\\mathcal{B}_n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can arrive at this splitting in two common ways:\n",
    "1. Let $A_n = f'(U^n)$ (the Jacobian) and then let\n",
    "$$\n",
    "    \\mathcal{B}_n(u) = f(u) - A_n u.\n",
    "$$\n",
    "1. If we know more about the structure of $f(u)$ we can leverage its structure to build $A_n$ and $\\mathcal{B}_n$.  Consider for example if we had an advection-diffusion problem, if we discretize only the diffusion operator and set this to $A_n$ and let the (possibly nonlinear) advection terms be $\\mathcal{B}$.  The same applies to reaction-diffusion for non-stiff reaction terms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "From here we compute the matrix exponential to solve the $A_n$ part of the problem and use this to evaluate the explicit problem via a numerical method.  Note that if $A_n$ is constant we can actually compute the matrix exponential once and continue to apply it without any extra computation. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "So how does this work?  Consider Duhamel's principle in the case we have proposed:\n",
    "$$\n",
    "    u(t_{n+1}) = e^{A_n \\Delta t} u(t_n) + \\int^{t_{n+1}}_{t_n} e^{A_n (t_{n+1} - \\tau)} \\mathcal{B}_n(u(\\tau)) d\\tau.\n",
    "$$\n",
    "We must approximate the integral due to $\\mathcal{B}_n(u(\\tau))$.  There are of course multiple ways to approach the approximation to varying orders but let's consider the first order method where we simply evaluate $\\mathcal{B}_n(U^n)$ and pull it out of the integral and evaluate the matrix exponential of the integral to find\n",
    "$$\\begin{aligned}\n",
    "    \\int^{t_{n+1}}_{t_n} e^{A_n (t_{n+1} - \\tau)} d\\tau &= \\Delta t + \\frac{\\Delta t^2}{2} A_n + \\frac{\\Delta t^3}{6} A^2_n + \\cdots \\\\\n",
    "    &= A^{-1}_n \\left( e^{A_n \\Delta t} - I \\right)\n",
    "\\end{aligned}$$\n",
    "assuming $A_n$ is non-singular."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "From here we can obtain the numerical method\n",
    "$$\n",
    "    U^{n+1} = e^{A_n \\Delta t} U^n + A^{-1}_n \\left( e^{A_n \\Delta t} - I \\right) \\mathcal{B}_n(U^n).\n",
    "$$\n",
    "In the first, more general case above we can write \n",
    "$$\n",
    "    \\mathcal{B}(U^n) = f(U^n) - A_n U^n\n",
    "$$\n",
    "we can rewrite the above as\n",
    "$$\n",
    "    U^{n+1} = U^n + A^{-1}_n \\left( e^{A_n \\Delta t} - I \\right) f(U^n).\n",
    "$$\n",
    "Here we can also identify this as related to forward Euler as the case where $A_n = 0$ reduces to exactly forward Euler."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can compute the truncation error as\n",
    "$$\\begin{aligned}\n",
    "    \\tau^n &= \\left(\\frac{u(t_{n+1}) - u(t_n)}{\\Delta t}\\right ) - \\frac{1}{\\Delta t} A^{-1}_n \\left(e^{A_n \\Delta t} - I \\right ) u'(t_n) \\\\\n",
    "    &= \\left[ u'(t_n) + \\frac{\\Delta t}{2} u''(t_n) + \\frac{\\Delta t^2}{6} u'''(t_n) + \\cdots \\right ] - \\left[ I + \\frac{\\Delta t}{2} A_n + \\frac{\\Delta t^2}{6} A^2_n + \\cdots \\right ] u'(t_n) \\\\\n",
    "    &= \\frac{\\Delta t}{2} (u''(t_n) - A_n u'(t_n)) + \\frac{\\Delta t^2}{6} (u'''(t_n) - A_n u'(t_n)) + \\cdots \\\\\n",
    "    &= \\frac{\\Delta t}{2} (f'(u(t_n)) - A_n) u'(t_n) + \\mathcal{O}(\\Delta t^2)\n",
    "\\end{aligned}$$\n",
    "therefore the method is second order accurate if $A_n \\equiv f'(U^n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can of course use higher-order methods to approximate the integral including multi-step methods (i.e. using an interpolating polynomial in time) or multi-stage Runge-Kutta like methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Equations that have dispersive terms in them, such as the KdV equation\n",
    "$$\n",
    "    u_t + uu_x = u_{xxx}\n",
    "$$\n",
    "can be particularly amenable to this approach.\n",
    "Note that here the linear operator would be the dispersive term and using the ETD approach, trying to solve this term exactly, has a huge advantage over attempting to solve this term numerically."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  },
  "latex_envs": {
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 0
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}