03_high_resolution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "<table>\n",
    " <tr align=left><td><img align=left src=\"./images/CC-BY.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": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "\n",
    "%matplotlib inline\n",
    "import numpy\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation\n",
    "from IPython.display import HTML\n",
    "\n",
    "import os\n",
    "import pyclaw\n",
    "path = os.path.join(os.environ.get(\"CLAW\", os.getcwd()), \"pyclaw\", \"fvmbook\", \"chap6\")\n",
    "os.chdir(path)\n",
    "import advection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# High-Resolution Methods\n",
    "\n",
    "The general approach we will take to augmenting our wave propagation methodology is to add correction terms in the following way:\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\frac{\\Delta t}{\\Delta x} \\left (\\mathcal{A}^+ \\Delta Q_{i-1/2} + \\mathcal{A}^- \\Delta Q_{i+1/2}  \\right) - \\frac{\\Delta t}{\\Delta x} \\left (\\widetilde{F}_{i+1/2} - \\widetilde{F}_{i-1/2} \\right)\n",
    "$$\n",
    "where here we have written these corrections as fluxes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Lax-Wendroff Method\n",
    "\n",
    "The first approach we will investigate is the Lax-Wendroff method derived from a Taylor series approach.  Recall that the Taylor series of our solution has the form\n",
    "$$\n",
    "    q(x, t_{n+1}) = q(x, t_n) + \\Delta t q_t(x, t_n) + \\frac{1}{2} \\Delta t^2 q_{tt}(x, t_n) + \\ldots\n",
    "$$\n",
    "If we consider solving the linear advection problem $q_t + A q_x = 0$ and assume *smooth solutions* then we can replace time derivatives with spatial derivatives in our Taylor series above where $q_t = -A q_x$ to find\n",
    "$$\n",
    "    q(x, t_{n+1}) = q(x, t_n) - \\Delta t A q_x(x, t_n) + \\frac{1}{2} \\Delta t^2 q_{tt}(x, t_n) + \\ldots\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Taking the second time derivative of $q_t = -A q_x$ leads to\n",
    "$$\\begin{aligned}\n",
    "    \\frac{\\partial}{\\partial t} (q_t) =& \\frac{\\partial}{\\partial t}(-A q_x) \\\\\n",
    "    q_{tt} =& -A (q_x)_t \\\\\n",
    "    q_{tt} =&  A^2 q_{xx}.\n",
    "\\end{aligned}$$\n",
    "Plugging this in again into our Taylor series we now have\n",
    "$$\n",
    "    q(x, t_{n+1}) = q(x, t_n) - \\Delta t A q_x(x, t_n) + \\frac{1}{2} \\Delta t^2 A^2 q_{xx}(x, t_n) + \\ldots\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Replacing the spatial derivatives with second order finite differences then leads us to the Lax-Wendroff method\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\frac{\\Delta t}{2 \\Delta x} (Q^n_{i+1} - Q^n_{i-1}) + \\frac{1}{2} \\left(\\frac{\\Delta t}{\\Delta x}\\right)^2 A^2 (Q^n_{i+1} - Q^n_i + Q^n_{i-1}).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This can again be interpreted as a finite volume method with the flux function defined as\n",
    "$$\n",
    "    F^n_{i-1/2} =\\frac{1}{2} A (Q^n_{i-1} + Q^n_i) - \\frac{1}{2} \\frac{\\Delta t}{\\Delta x} A^2 (Q^n_i - Q^n_{i-1})\n",
    "$$\n",
    "As mentioned before this looks like the unstable flux with a diffusive correction term.  From a method of lines and absolute stability point-of-view this is exactly what pushed the eigenvalues into the absolute stability region of forward Euler."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def q_true(t, IC='gauss_square'):\n",
    "    # True Solution\n",
    "    x_true = numpy.linspace(0.0, 1.0, 1000)\n",
    "    x_shift = x_true - t\n",
    "    x_shift = numpy.mod(x_shift, 1.0)\n",
    "    if IC == 'gauss_square':\n",
    "        x1 = 0.6; x2 = 0.8\n",
    "        beta=200.; x0=0.3; mx=100\n",
    "        q_true = numpy.exp(-beta * (x_shift-x0)**2) + (x_shift>0.6)*(x_shift<0.8)\n",
    "    elif IC == 'wavepacket':\n",
    "        beta=100.; x0=0.5; mx=100\n",
    "        q_true = numpy.exp(-beta * (x_shift-x0)**2) * sin(80.*x_shift)\n",
    "    return q_true\n",
    "\n",
    "def advection_animation(solver_order=2, limiters=0, IC='gauss_square'):\n",
    "   \n",
    "    # compute the solution with the method define above:\n",
    "    claw = advection.fig_61_62_63(solver_order=solver_order, limiters=limiters)\n",
    "    claw.keep_copy = True\n",
    "    claw.run()\n",
    "    x = claw.frames[0].grid.dimensions[0].centers\n",
    "    x_true = numpy.linspace(0.0, 1.0, 1000)\n",
    "    \n",
    "    fig = plt.figure()\n",
    "    axes = plt.subplot(1, 1, 1)\n",
    "    axes.set_xlim((x[0], x[-1]))\n",
    "    axes.set_ylim((-0.1, 1.1))\n",
    "    axes.set_title(\"Lax-Wendroff\")\n",
    "    \n",
    "    def init():\n",
    "        axes.set_xlim((x[0], x[-1]))\n",
    "        axes.set_ylim((-0.1, 1.1))\n",
    "        computed_line, = axes.plot(x[0], claw.frames[0].q[0, :][0], 'ro')\n",
    "        exact_line, = axes.plot(x_true[0], q_true(0.0)[0], 'k')\n",
    "        return (computed_line, exact_line)\n",
    "    \n",
    "    computed_line, exact_line = init()\n",
    "    \n",
    "    def fplot(n):\n",
    "        computed_line.set_data([x,], [claw.frames[n].q[0, :]])\n",
    "        exact_line.set_data([x_true], [q_true(claw.frames[n].t)])\n",
    "        return (computed_line, exact_line)\n",
    "\n",
    "    frames_to_plot = range(0, len(claw.frames))\n",
    "    plt.close(fig)\n",
    "    return matplotlib.animation.FuncAnimation(fig, fplot, frames=frames_to_plot, interval=100,\n",
    "                                   blit=True, init_func=init, repeat=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "HTML(advection_animation(solver_order=2, limiters=0, IC='gauss_square').to_jshtml())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Beam-Warming Method\n",
    "Another approach to second order accuracy is to instead use one-sided or upwinded derivative approximations.  With the same Taylor series approach if we instead replace the spatial derivatives with upwinded differences we then have\n",
    "$$\\begin{aligned}\n",
    "    q_x(x_i,t_n) &= \\frac{1}{2\\Delta x} [3 q(x_i, t_n) - 4q(x_{i-1}, t_n) + q(x_{i-2}, t_n)] + \\mathcal{O}(\\Delta x^2) \\\\\n",
    "    q_{xx}(x_i,t_n) &= \\frac{1}{\\Delta x^2} [q(x_i, t_n) - 2q(x_{i-1}, t_n) + q(x_{i-2}, t_n)] + \\mathcal{O}(\\Delta x^2) \\\\\n",
    "\\end{aligned}$$\n",
    "leading to\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\frac{\\Delta t}{2 \\Delta x} A (3 Q^n_i - 4 Q^n_{i-1} + Q^n_{i-2} ) + \\frac{1}{2} \\left(\\frac{\\Delta t}{\\Delta z} \\right)^2 A^2 (Q^n - 2 Q^n_{i-1} + Q^n_{i-2})\n",
    "$$\n",
    "or in flux form\n",
    "$$\n",
    "    F^n_{i-1/2} = A Q^n_{i-1} + \\frac{1}{2} A \\left ( 1 - \\frac{\\Delta t}{\\Delta x} A \\right) (Q^n_{i-1} - Q^n_{i-2}).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Preview of Limiters\n",
    "\n",
    "Given that higher order methods work well in smooth regions while lower order methods work better in regions where high gradients or discontinuities exist we will pursue a way to combine the advantages of both and decide dynamically what type of method to use.  This is the primary role of a limiter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As a first examination of this idea consider the numerical flux for the Lax-Wendroff method rewritten in the form\n",
    "$$\n",
    "    F^n_{i-1/2} = (A^- Q^n_i + A^+Q^n_{i-1}) + \\frac{1}{2} |A| \\left ( I - \\frac{\\Delta t}{\\Delta x} |A| \\right) (Q^n_i - Q^n_{i-1})\n",
    "$$\n",
    "This is therefore the upwind flux with a correction term added similar to how we suggested in the beginning of this lecture."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also rewrite the previous flux then as\n",
    "$$\\begin{aligned}\n",
    "    F^n_{i-1/2} &= (A^- Q^n_i + A^+Q^n_{i-1}) + \\frac{1}{2} |A| \\left ( I - \\frac{\\Delta t}{\\Delta x} |A| \\right) (Q^n_i - Q^n_{i-1}) \\\\\n",
    "    &=\\mathcal{F}_L(Q_{i-1}, Q_i) + \\Phi^n_{i-1/2} [\\mathcal{F}_H(Q_{i-1}, Q_i) - \\mathcal{F}_L(Q_{i-1}, Q_i)]\n",
    "\\end{aligned}$$\n",
    "\n",
    "In this form if $\\Phi^n_{i-1/2} = 0$ then this reduces to the low-order method and if $\\Phi^n_{i-1/2} = 1$ then we get the high-order method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "### Compare several methods for advecting a Gaussian and square wave.\n",
    "### \n",
    "### The settings coded here are for Figure 6.1(a).\n",
    "### For Figure 6.1(b), set solver.order=2.\n",
    "### For Figure 6.2(a), set solver.order=2 and solver.limiters = pyclaw.limiters.tvd.minmod (1)\n",
    "### For Figure 6.2(b), set solver.order=2 and solver.limiters = pyclaw.limiters.tvd.superbee (2)\n",
    "### For Figure 6.2(c), set solver.order=2 and solver.limiters = pyclaw.limiters.tvd.MC (4)\n",
    "\n",
    "# HTML(advection_animation(solver_order=2, limiters=0, IC='gauss_square').to_jshtml())\n",
    "# HTML(advection_animation(solver_order=2, limiters=1, IC='gauss_square').to_jshtml())\n",
    "# HTML(advection_animation(solver_order=2, limiters=2, IC='gauss_square').to_jshtml())\n",
    "HTML(advection_animation(solver_order=2, limiters=4, IC='gauss_square').to_jshtml())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## The REA Algorithm with Piecewise Linear Reconstruction\n",
    "\n",
    "In the REA algorithm we have the following steps:\n",
    "\n",
    "1. Reconstruct\n",
    "1. Evolve\n",
    "1. Average\n",
    "\n",
    "One of the ways to understand higher-oder methods is to modify the *reconstruct* step to higher-order polynomials."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "From the cell averages $Q^n_i$ we need to construct piecewise linear functions such that\n",
    "$$\n",
    "    \\widetilde{q}^n(x, t_n) = Q^n_i + \\sigma^n_i (x - x_i) \\quad \\text{for } x_{i-1/2} \\leq x \\leq x_{i+1/2}\n",
    "$$\n",
    "assuming that x_i is the cell center.  We now need to figure out how to determine the slope $\\sigma^n_i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "If we assume $u > 0$ we can compute for linear advection $q_t + u q_x = 0$ that the update formula that correct solution to this problem should be\n",
    "$$\\begin{aligned}\n",
    "    Q^{n+1}_i &= \\frac{u \\Delta t}{\\Delta x} \\left(Q^n_{i-1} + \\frac{1}{2} (\\Delta x - u \\Delta t) \\sigma^n_{i-1} \\right) + \\left(1 - \\frac{u \\Delta t}{\\Delta x} \\right) \\left ( Q^n_i - \\frac{1}{2} u \\Delta t \\sigma^n_i \\right) \\\\\n",
    "    &= Q^n_i - \\frac{u \\Delta t}{\\Delta x}(Q^n_i - Q^n_{i-1} ) - \\frac{1}{2} \\frac{u \\Delta t}{\\Delta x} (\\Delta x - u \\Delta t) (\\sigma^n_i - \\sigma^n_{i-1})\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Choice of Slopes\n",
    "\n",
    "We still have yet to specify which slope we would like to use for $\\sigma^n_i$.  For a linear reconstruction we have three options:\n",
    "$$\\begin{aligned}\n",
    "    &\\text{Centered} & & \\sigma^n_i = \\frac{Q^n_{i+1} - Q^n_{i-1}}{2 \\Delta x} && \\text{(Fromm)} \\\\\n",
    "    &\\text{Upwind Slope} & & \\sigma^n_i = \\frac{Q^n_{i} - Q^n_{i-1}}{\\Delta x} && \\text{(Beam-Warming)} \\\\\n",
    "    &\\text{Downwind Slope} & & \\sigma^n_i = \\frac{Q^n_{i+1} - Q^n_{i}}{\\Delta x} && \\text{(Lax-Wendroff)}\n",
    "\\end{aligned}$$\n",
    "At this point it is not clear exactly which slope might be the best."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Oscillations\n",
    "\n",
    "One of the key observations from the Lax-Wendroff or Beam-Warming methods is that spurious oscillations end up being created.  From modified equation analysis this is not surprising given that the leading error terms are dispersive in nature.  In the context of hyperbolic PDEs we would like to avoid these oscillations as they are generally not indicative of true solutions.  In fact, at a discontinuity we know that in many instances that the solution should dissipating energy or smoothing the solution physically.  Therefore we will seek to remove these oscillations from our solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Total Variation\n",
    "\n",
    "To provide a concrete way to *limit* the slope we will introduce a mathematical way to measure oscillations.\n",
    "\n",
    "The **total variation** for a grid function $Q$ is defined as\n",
    "$$\n",
    "    \\text{TV}(Q) = \\sum^\\infty_{i=-\\infty} |Q_i - Q_{i-1} |\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also define for a function this metric as \n",
    "$$\n",
    "    \\text{TV}(q(x)) = \\sup \\sum^N_{j=1} |q(\\xi_j) - q(\\xi_{j-1}) |\n",
    "$$\n",
    "Another definition is\n",
    "$$\n",
    "    \\text{TV}(q) = \\limsup_{\\epsilon \\rightarrow 0} \\frac{1}{\\epsilon} \\int^\\infty_{-\\infty} |q(x) - q(x - \\epsilon)|dx\n",
    "$$\n",
    "which reduces to\n",
    "$$\n",
    "    \\text{TV}(q) = \\int^\\infty_{-\\infty} |q'(x)|dx\n",
    "$$\n",
    "if $q$ is differentiable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A two-level method is called **total variation diminishing** (TVD) if, for any set of data $Q^n$, the values $Q^{n+1}$ computed by the method satisfies\n",
    "$$\n",
    "    \\text{TV}(Q^{n+1}) \\leq \\text{TV}(Q^n).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One important consequence of a TVD method is that if data is initially monotone in the sense that\n",
    "$$\n",
    "    Q^n_i \\leq Q^n_{i+1} \\text{    or    } Q^n_i \\geq Q^n_{i+1} \\quad \\forall i\n",
    "$$\n",
    "then this will hold for all future time.  This leads us to the next definition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A method is called **monotonicity-preserving** if \n",
    "$$\n",
    "    Q^n_i \\geq Q^n_{i+1} \\forall i \\Rightarrow Q^{n+1}_i \\geq Q^{n+1}_{i+1} \\forall i\n",
    "$$\n",
    "Any TVD method is monotonicity preserving."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "How then can we derive a TVD method?  If we follow the REA algorithm then in the reconstruction phase we can require\n",
    "$$\n",
    "    \\text{TV}(\\widetilde{q}^n(x, t_n)) \\leq \\text{TV}(Q^n)\n",
    "$$\n",
    "so that our resulting evolved function should remain TVD.  This can be clearly seen as the evolve step will also maintain this relationship as will the averaging."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Slope-Limiter Methods\n",
    "\n",
    "Now that we have established some basis as to how we may want to reconstruct functions let us return to the question of reconstructing the slopes $\\sigma$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One choice of slope that maintains second-order accuracy and the TVD property is the **minmod slope** defined as \n",
    "$$\n",
    "    \\sigma^n_i = \\text{minmod}\\left( \\frac{Q^n_i - Q^n_{i-1}}{\\Delta x}, \\frac{Q^n_{i+1} - Q^n_{i}}{\\Delta x} \\right)\n",
    "$$\n",
    "where\n",
    "$$\n",
    "    \\text{minmod}(a, b) = \\left \\{ \\begin{aligned}\n",
    "        a & & \\text{if } |a| < |b| \\text{ and } ab > 0 \\\\\n",
    "        b & & \\text{if } |b| < |a| \\text{ and } ab > 0 \\\\\n",
    "        0 & & \\text{if } ab \\leq 0 \\\\\n",
    "    \\end{aligned} \\right .\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Compositions of the minmod function also form a number of slope choices.  One in particular is the **monotonized central-difference limiter** (MC)\n",
    "$$\n",
    "    \\sigma^n_i = \\text{minmod}\\left( \\left (\\frac{Q^n_{i+1} - Q^n_{i-1}}{2 \\Delta x} \\right ), 2\\left(\\frac{Q^n_i - Q^n_{i-1}}{\\Delta x} \\right), 2 \\left (\\frac{Q^n_{i+1} - Q^n_{i}}{\\Delta x} \\right ) \\right )\n",
    "$$\n",
    "Note that these still represent finite difference approximations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Flux Formulation with Piecewise Linear Reconstruction\n",
    "\n",
    "Using these reconstructed slopes how does this now impact our flux formulations?  Let us turn to the basic definition of a flux function then and see how it is impacted by our reconstruction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "$$\\begin{aligned}\n",
    "    F^n_{i-1/2} &= \\frac{1}{\\Delta t} \\int^{t_{n+1}}_{t_n} u \\widetilde{q}^n(x_{i-1/2}, t) dt \\\\\n",
    "    &= \\frac{1}{\\Delta t} \\int^{t_{n+1}}_{t_n} u \\widetilde{q}^n(x_{i-1/2} - u(t - t_n), t_n) dt \\\\\n",
    "    &= \\frac{1}{\\Delta t} \\int^{t_{n+1}}_{t_n} u \\left[ Q^n_{i-1} + (x_{i-1/2} - u (t - t_n) - x_{i-1} ) \\sigma^n_{i-1} \\right] dt \\\\\n",
    "    &= u Q^n_{i-1} + \\frac{1}{2} u (\\Delta x - u \\Delta t) \\sigma^n_{i-1} \\\\\n",
    "\\end{aligned}$$\n",
    "Plugging this into our original updating formula leads to\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\frac{u \\Delta t}{\\Delta x} (Q^n_i - Q^n_{i-1} ) - \\frac{1}{2} \\frac{u \\Delta t}{\\Delta x} (\\Delta x  - u \\Delta t) (\\sigma^n_i - \\sigma^n_{i-1})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also think instead of limiting the fluxes between cells to update our first-order methods to higher-order.  If we define\n",
    "$$\n",
    "    \\Delta Q^n_{i-1/2} \\equiv Q^n_i - Q^n_{i-1}\n",
    "$$\n",
    "and then define a flux such that\n",
    "$$\n",
    "    F^n_{i-1/2} = u^- Q^n_i + u^+ Q^n_{i-1} + \\frac{1}{2} |u| \\left ( 1- \\left |\\frac{u \\Delta t}{\\Delta x} \\right |\\right) \\delta^n_{i-1/2}\n",
    "$$\n",
    "where\n",
    "$$\n",
    "    \\delta^n_{i-1/2} \\equiv \\text{limited} (\\Delta Q^n_{i-1/2})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Flux Limiters\n",
    "\n",
    "We can now start to make connections between our desire for high-order methods, limiting, and TVD.  Lax-Wendroff for instance is simply interpretable as the piecewise linear reconstruction in the most straight-forward way as as central difference.  Let us meld the rest of the methods and others by generalizing this idea a bit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let\n",
    "$$\n",
    "    \\delta^n_{i-1/2} = \\phi(\\theta^n_{i-1/2}) \\Delta Q^n_{i-1/2}\n",
    "$$\n",
    "where\n",
    "$$\n",
    "    \\theta^n_{i-1/2} = \\frac{\\Delta Q^n_{I-1/2}}{\\Delta Q^n_{i-1/2}}\n",
    "$$\n",
    "and\n",
    "$$\n",
    "    I = \\left \\{ \\begin{aligned}\n",
    "        i - 1 & & \\text{if } u > 0 \\\\\n",
    "        i + 1 & & \\text{if } u < 0\n",
    "    \\end{aligned} \\right .\n",
    "$$\n",
    "Basically we are \"measuring\" the smoothness of the function $Q$ using $\\theta$.  We then want the function $\\phi$ to \"limit\" the slope based on the smoothness of $Q$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One interesting case is to choose\n",
    "$$\n",
    "    \\phi(\\theta) = \\theta\n",
    "$$\n",
    "where\n",
    "$$\n",
    "    \\delta^n_{i-1/2} = \\left( \\frac{\\Delta Q^n_{I-1/2}}{\\Delta Q^n_{i-1/2}} \\right) \\Delta Q^n_{i-1/2} = \\Delta Q^n_{I-1/2}\n",
    "$$\n",
    "which reduces to the upwind scheme and therefore the Beam-Warming method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Given this framework we can then define the following set of methods:\n",
    "\n",
    "Linear Methods:\n",
    "$$\\begin{aligned}\n",
    "    \\text{upwind:} & & \\phi(\\theta) &= 0 \\\\\n",
    "    \\text{Lax-Wendroff:} & & \\phi(\\theta) &= 1 \\\\\n",
    "    \\text{Beam-Warming:} & & \\phi(\\theta) &= \\theta \\\\\n",
    "    \\text{Fromm:} & & \\phi(\\theta) &= \\frac{1}{2} (1 + \\theta) \\\\\n",
    "\\end{aligned}$$\n",
    "\n",
    "High-Resolution (non-linear) Methods:\n",
    "$$\\begin{aligned}\n",
    "    \\text{minmod:} & & \\phi(\\theta) &= \\text{minmod}(1, \\theta) \\\\\n",
    "    \\text{superbee:} & & \\phi(\\theta) &= \\max(0, \\min(1, 2\\theta), \\min(2, \\theta) \\\\\n",
    "    \\text{MC:} & & \\phi(\\theta) &= \\max(0, \\min((1+\\theta)/2, 2, 2 \\theta)\\\\\n",
    "    \\text{van Leer:} & & \\phi(\\theta) &= \\frac{\\theta + |\\theta|}{1 + |\\theta|} \\\\\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## TVD Limiters\n",
    "\n",
    "Returning back to our desire for having a TVD scheme we need to ask the question, which of our limiters will make our scheme TVD?  This is at times for linear limiters easy to check but we need something a bit more powerful for the non-linear limiters we have introduced."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Harten**: Consider a general method of the form\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - C^n_{i-1} (Q^n_i - Q^n_{i-1}) + D^n_i (Q^n_{i+1} - Q^n_i)\n",
    "$$\n",
    "over one time step, where the coefficients $C^n_{i-1}$ and $D^n_i$ are arbitrary (which can depend on values of Q^n in particular).  Then\n",
    "$$\n",
    "    \\text{TV}(Q^{n+1}) \\leq \\text{TV}(Q^n)\n",
    "$$\n",
    "provided the following conditions are satisfied\n",
    "$$\\begin{aligned}\n",
    "    C^n_{i-1} \\geq 0 & & \\forall i \\\\\n",
    "    D^n_{i} \\geq 0 & & \\forall i \\\\\n",
    "    C^n_{i} + D^n_i \\leq 1 & & \\forall i \\\\\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's apply this theorem to the flux limiter method for the advection equation where $u > 0$.  First the general flux update form looks like \n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\nu (Q^n_i - Q^n_{i-1} ) - \\frac{1}{2} \\nu (1 - \\nu) [\\phi(\\theta^n_{i+1/2}) (Q^n_{i+1} - Q^n_i) - \\phi(\\theta^n_{i-1/2}) (Q^n_i - Q^n_{i-1})]\n",
    "$$\n",
    "for flux limiters replacing the $u \\Delta t / \\Delta x$ with $\\nu$.  Try to write this in the form from Harten first."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can write this with\n",
    "$$\n",
    "    C^n_{i-1} = \\nu - \\frac{1}{2} \\nu (1 - \\nu) \\phi(\\theta^n_{i-1/2}) \\\\\n",
    "    D^n_i = -\\frac{1}{2} \\nu (1 - \\nu) \\phi(\\theta^n_{i-1/2})\n",
    "$$\n",
    "but this is not sufficient to show the method is TVD via Harten's theorem.  However, if $0 \\leq \\nu \\leq 1$ then $D < 0$ when $\\phi \\approx 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One thing to note however is that \n",
    "$$\n",
    "    Q^n_{i+1} - Q^n_i = \\frac{Q^n_i - Q^n_{i-1} }{\\theta^n_{i+1/2}}\n",
    "$$\n",
    "so that our original form can actually be written so that\n",
    "$$\n",
    "    C^n_{i-1} = \\nu + \\frac{1}{2} \\nu (1 - \\nu) \\left[ \\frac{\\phi(\\theta^n_{i+1/2} )}{\\theta^n_{i+1/2}} - \\phi(\\theta^n_{i-1/2} ) \\right] \\\\\n",
    "    D^n_i = 0\n",
    "$$\n",
    "so that the conditions are satisfied if\n",
    "$$\n",
    "    0 \\leq C^n_{i-1} \\leq 1\n",
    "$$\n",
    "which in turn holds if $0 \\leq \\nu \\leq 1$ as well as the bound\n",
    "$$\n",
    "    \\left | \\frac{\\phi(\\theta_1)}{\\theta_1} - \\phi(\\theta_2) \\right | \\leq 2 \\quad \\forall \\theta_1, \\theta_2.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A couple of interesting cases result from this realization:\n",
    "1. $\\theta \\leq 0$: we are at an extremum and we know that $\\phi(\\theta) = 0$.\n",
    "1. $\\theta > 0$: we want $\\phi(\\theta) > 0$ as we do not want to negate the sign of the slope"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Also we can also disentangle the bound to find\n",
    "$$\n",
    "    0 \\leq \\frac{\\phi(\\theta)}{\\theta} \\leq 2 \\quad \\text{and} \\quad 0 \\leq \\phi(\\theta) \\leq 2.\n",
    "$$\n",
    "for all values $\\phi(\\theta) \\geq 0$.  This can be rewritten as\n",
    "$$\n",
    "    0 \\leq \\phi(\\theta) \\leq \\text{minmod}(2, 2\\theta).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Often we also may want to require the the function $\\phi$ be symmetric implying that\n",
    "$$\n",
    "    \\phi(1 / \\theta) = \\frac{\\phi(\\theta)}{\\theta}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Methods for Systems\n",
    "\n",
    "All of these methods of course also apply to systems of hyperbolic PDEs.  If we look at the flux differencing form of Lax-Wendroff\n",
    "$$\n",
    "    \\mathcal{F}(Q_{i-1}, Q_i) = \\frac{1}{2} A (Q_{i-1} + Q_i) - \\frac{1}{2} \\frac{\\Delta t}{\\Delta x} A^2 (Q_i - Q_{i-1})\n",
    "$$\n",
    "and recall that $A = A^+ + A^-$ we can rewrite this as\n",
    "$$\n",
    "    \\mathcal{F}(Q_{i-1}, Q_i) = (A^+ Q_{i-1} + A^- Q_i) + \\frac{1}{2} |A| \\left( I - \\frac{\\Delta t}{\\Delta x} |A| \\right )(Q_i - Q_{i-1}).\n",
    "$$\n",
    "This has the form of an upwind, first-order term with the added correction due to Lax-Wendroff.  We will need to limit this correction term."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "First rewrite the correction term from before as\n",
    "$$\n",
    "    \\frac{1}{2} |A| \\left( I - \\frac{\\Delta t}{\\Delta x} |A| \\right )(Q_i - Q_{i-1}) = \\frac{1}{2} |A| \\left( I - \\frac{\\Delta t}{\\Delta x} |A| \\right ) \\sum^m_{p=1} \\alpha^p_{i-1/2} r^p\n",
    "$$\n",
    "effectively writing the jump $\\Delta Q_{i-1/2}$ in terms of the waves or otherwise projecting the jump onto the eigenvectors of $A$.  If we replace the coefficient $\\alpha$ with a limited version, i.e.\n",
    "$$\n",
    "    \\widetilde{\\alpha}^p_{i-1/2} = \\alpha^p_{i-1/2} (\\theta^p_{i-1/2})\n",
    "$$\n",
    "where\n",
    "$$\n",
    "    \\theta^p_{i-1/2} = \\frac{\\alpha^p_{I-1/2}}{\\alpha^p_{i-1/2}}\n",
    "$$\n",
    "with the $I$ from before."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can then write the original flux as \n",
    "$$\n",
    "    \\mathcal{F}(Q_{i-1}, Q_i) = (A^+ Q_{i-1} + A^- Q_i) + \\frac{1}{2} |A| \\left( I - \\frac{\\Delta t}{\\Delta x} |A| \\right ) \\sum^m_{p=1} \\widetilde{\\alpha}^p_{i-1/2} r^p\n",
    "$$\n",
    "or using the fact that $|A| r^p = |\\lambda^p| r^p$ we get\n",
    "$$\n",
    "    \\mathcal{F}(Q_{i-1}, Q_i) = (A^+ Q_{i-1} + A^- Q_i) + \\frac{1}{2} \\sum^m_{p=1}  \\left( 1 - \\frac{\\Delta t}{\\Delta x} |\\lambda^p| \\right ) \\widetilde{\\alpha}^p_{i-1/2} r^p.\n",
    "$$\n",
    "Another useful way to write this is in terms of limited waves defined by\n",
    "$$\n",
    "    \\widetilde{\\mathcal{W}}^p_{i-1/2} = \\widetilde{\\alpha}^p_{i-1/2} r^p.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Wave-Propagation Implementation\n",
    "\n",
    "We now turn to implementing this in the wave-propagation form and is the way that Clawpack implements these algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "First look at the general form where the upwinding terms and limited flux difference are easy to identify:\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\frac{\\Delta t}{\\Delta x} (A^+ \\Delta Q_{i-1/2} + A^- \\Delta Q_{i+1/2} ) - \\frac{\\Delta t}{\\Delta x} (\\widetilde{F}_{i+1/2} - \\widetilde{F}_{i-1/2}).\n",
    "$$\n",
    "Now we replace everything with our waves with\n",
    "$$\\begin{aligned}\n",
    "    A^+ \\Delta Q_{i-1/2} &= \\sum^{m}_{p=1} (\\lambda^p)^+ \\mathcal{W}^p_{i-1/2} \\\\\n",
    "    A^- \\Delta Q_{i-1/2} &= \\sum^{m}_{p=1} (\\lambda^p)^- \\mathcal{W}^p_{i-1/2} \\\\\n",
    "    \\widetilde{F}_{i-1/2} &= \\frac{1}{2} \\sum^m_{p=1}  \\left( I - \\frac{\\Delta t}{\\Delta x} |\\lambda^p| \\right ) \\widetilde{\\mathcal{W}}^p_{i-1/2}\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Non-Linear Systems\n",
    "\n",
    "In general all the methods mentioned so far can easily be applied to nonlinear systems as well.  We can do this by knowing that in general we are still solving Riemann problems that yield a set of waves $\\mathcal{W}^p_{i-1/2}$ and speeds $s^p_{i-1/2}$ that can be treated analogously  to the linear problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Along with this generalization we will define the following more general quantities:\n",
    "$$\\begin{aligned}\n",
    "    \\mathcal{A}^- \\Delta Q_{i-1/2} &= \\sum^m_{p=1} (s^p_{i-1/2})^- \\mathcal{W}^p_{i-1/2}\\\\\n",
    "    \\mathcal{A}^+ \\Delta Q_{i-1/2} &= \\sum^m_{p=1} (s^p_{i-1/2})^+ \\mathcal{W}^p_{i-1/2}\n",
    "\\end{aligned}$$\n",
    "and requiring\n",
    "$$\\begin{aligned}\n",
    "    \\mathcal{A}^- \\Delta Q_{i-1/2} + \\mathcal{A}^+ \\Delta Q_{i-1/2} = f(Q_i) - f(Q_{i-1})\n",
    "\\end{aligned}$$\n",
    "as before.  There are additional issues that will be addressed when we start to study the nonlinear problem in more general."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}