<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II.  Approximate Riemann Solvers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Part II of this book we present a number of *approximate Riemann solvers*.  We have already seen that for many important hyperbolic systems it is possible to work out the exact Riemann solution for arbitrary left and right states.  However, for complicated nonlinear problems this exact solution can only be determined by solving a nonlinear system of algebraic equations for the intermediate states and the waves that connect them.  This can be done to arbitrary precision, but only at some computational expense.  The cost of exactly solving a single Riemann problem may seem insignificant, but it can become prohibitively expensive when the Riemann solver is used as a building block in a finite volume method.  In this case a Riemann problem must be solved at every cell edge at every time step.\n",
    "\n",
    "For example, if we consider a very coarse grid in one space dimension with only 100 cells and take 100 time steps, then 10,000 Riemann problems must be solved.  In solving practical problems in two or three space dimensions it is not unusual to require the solution of billions or trillions of Riemann problems. In this context it can be very important to develop efficient approximate Riemann solvers that quickly produce a sufficiently good approximation to the true Riemann solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is useful to keep the following points in mind:\n",
    "\n",
    " - If the solution is smooth over much of the domain, then the jump in states between neighboring cells will be very small (on the order of $\\Delta x$, the cell size) for most of the Riemann problems encountered in the numerical solution. Even if the hyperbolic system being studied is nonlinear, for such data the equations can be approximated by a linearization and we have seen that linear Riemann problems can be solved more easily than nonlinear ones.  Rather than solving a nonlinear system of equations by some iterative method, one need only solve a linear system (provided the eigenvalues and eigenvectors of the Jacobian matrix are known analytically, as they often are for practical problems).  In many cases the solution of this linear system can also be worked out analytically and is easy to implement, so no linear algebra is required.  \n",
    " \n",
    " - In spite of smoothness over much of the domain, in interesting problems there are often isolated discontinuities such as shock waves that are important to model accurately.  So some Riemann problems arising in a finite volume method may have large jumps between the left and right states.  Hence a robust approximate Riemann solver must also handle these cases without introducing too much error.\n",
    " \n",
    " - But even in the case of large jumps in the data, it may not be necessary or worthwhile to solve the Riemann problem exactly.  The information produced by the Riemann solver goes into a numerical method that updates the approximate solution in each grid cell and the exact  structure of the Riemann solution is lost in the process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The notebooks in this part of the book will illustrate some common approximate Riemann solvers in the context of several different nonlinear systems.  \n",
    "\n",
    "We focus on two popular approaches to devising approximate Riemann solvers (not the only approaches):\n",
    "\n",
    " 1. Linearized Riemann solvers for a nonlinear system $q_t + f(q)_x = 0$. If $q_l$ and $q_r$ are close to each other, as is often the case over smooth regions of a more general solution, then the nonlinear system can be approximated by a linear problem of the form $q_t + \\hat A q_x = 0$.  The coefficient matrix $\\hat A$ should be some approximation to  $f'(q_l) \\approx f'(q_r)$ in the case where $\\|q_l-q_r\\|$ is small.  The idea of a general linearized Riemann solver is to define a function $\\hat A(q_l, q_r)$ that has this property but also makes sense as an approximation in the case when $\\|q_l-q_r\\|$ is not small.  For many nonlinear systems there is a *Roe linearization*, a particular function that works works very well based on ideas introduced originally by <NAME> <cite data-cite=\"Roe1981\"><a href=\"riemann.html#Roe1981\">(Roe, 1981)</a></cite>.  For systems such as the shallow water equations or the Euler equations, there are closed-form expressions for the eigenvalues and eigenvectors of $\\hat A$ and the solution of the linearized Riemann problem, leading to efficient solvers.  The Roe solver is explored in more detail in [several notebooks to appear].\n",
    " \n",
    " 2. HLL-type solvers.  A simple approach to generating an approximate solver for any hyperbolic conservation law along with other variants is discussed in <cite data-cite=\"HLL\"><a href=\"riemann.html#HLL\">(<NAME>, and van Leer)</a></cite>.  In the original HLL solver, two approximate wave speeds $s_1$ and $s_2$ are chosen and the approximate solution consists of only two waves propagating with these speeds (regardless of how many waves appear in the exact Riemann solution).  The intermediate state between the two waves is uniquely determined by the requirement that the approximate solution should be conservative.  Various improvements of this idea have been proposed more recently, giving rise to methods such as HLLE and HLLC.  These methods will also be explored in more detail in the future notebooks.\n",
    " \n",
    "See <cite data-cite=\"fvmhp\"><a href=\"riemann.html#fvmhp\">(LeVeque, 2002)</a></cite> for more discussion of approximate solvers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notation and structure of approximate solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In both the Roe and HLL approaches, the approximate Riemann solution consists entirely of traveling discontinuities.  Following <cite data-cite=\"HLL\"><a href=\"riemann.html#HLL\">(<NAME>, and <NAME>)</a></cite>, we refer to these traveling discontinuities as *waves*, and denote them by $\\wave^p$, where the index $p$ denotes the characteristic family and typically ranges from $1$ to $m$ for a system of $m$ equations.  For each wave, the approximate solver must also give a wave speed $s^p$.\n",
    "\n",
    "The net effect of each wave from the Riemann solution is given by the product of the wave and its speed.  In a finite volume scheme, the rate of change of the cell average to the left of a given interface is given by\n",
    "\n",
    "$$\\amdq = \\sum_{p=1}^m (s^p)^- \\wave^p$$\n",
    "\n",
    "and that to the right is given by\n",
    "\n",
    "$$\\apdq = \\sum_{p=1}^m (s^p)^+ \\wave^p$$\n",
    "\n",
    "where $(x)^- = \\min(x,0)$ and $(x)^+ = \\max(x,0)$.  We refer to $\\amdq, \\apdq$ as *fluctuations*.\n",
    "\n",
    "The purpose of an approximate Riemann solver, in this context, is to determine the waves $\\wave^p$ and speeds $s^p$; these can then be used to update the numerical solution via the fluctuations.\n",
    "\n",
    "A common, but different, viewpoint is that the Riemann solver must produce an approximation of the flux at $x=0$.  This can be used to update the numerical solution via a *flux-differencing* scheme. (*add more on the relation between fluctuations and fluxes*)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {<commit_msg>Revise intro to part two.<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II.  Approximate Riemann Solvers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Part II of this book we present a number of *approximate Riemann solvers*.  We have already seen that for many important hyperbolic systems it is possible to work out the exact Riemann solution for arbitrary left and right states.  However, for complicated nonlinear systems, such as the Euler equations (see [Euler_equations.ipynb](Euler_equations.ipynb), this exact solution can only be determined by solving a nonlinear system of algebraic equations for the intermediate states and the waves that connect them.  This can be done to arbitrary precision, but only at some computational expense.  The cost of exactly solving a single Riemann problem may seem insignificant, but it can become prohibitively expensive when the Riemann solver is used as a building block in a finite volume method.  In this case a Riemann problem must be solved at every cell edge at every time step.\n",
    "\n",
    "For example, if we consider a very coarse grid in one space dimension with only 100 cells and take 100 time steps, then 10,000 Riemann problems must be solved.  In solving practical problems in two or three space dimensions it is not unusual to require the solution of billions or trillions of Riemann problems. In this context it can be very important to develop efficient approximate Riemann solvers that quickly produce a sufficiently good approximation to the true Riemann solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following points have helped to guide the development of approximate Riemann solvers:\n",
    "\n",
    " - If the solution is smooth over much of the domain, then the jump in states between neighboring cells will be very small (on the order of $\\Delta x$, the cell size) for most of the Riemann problems encountered in the numerical solution. Even if the hyperbolic system being studied is nonlinear, for such data the equations can be approximated by a linearization and we have seen that linear Riemann problems can be solved more easily than nonlinear ones.  Rather than solving a nonlinear system of equations by some iterative method, one need only solve a linear system (provided the eigenvalues and eigenvectors of the Jacobian matrix are known analytically, as they often are for practical problems).  In many cases the solution of this linear system can also be worked out analytically and is easy to implement, so no linear algebra is required.  \n",
    " \n",
    " - In spite of smoothness over much of the domain, in interesting problems there are often isolated discontinuities such as shock waves that are important to model accurately.  So some Riemann problems arising in a finite volume method may have large jumps between the left and right states.  Hence a robust approximate Riemann solver must also handle these cases without introducing too much error.\n",
    " \n",
    " - But even in the case of large jumps in the data, it may not be necessary or worthwhile to solve the Riemann problem exactly.  The information produced by the Riemann solver goes into a numerical method that updates the approximate solution in each grid cell and the exact  structure of the Riemann solution is lost in the process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each chapter in this part of the book illustrates some common approximate Riemann solvers in the context of one of the nonlinear systems studied in part 1.  We focus on two popular approaches to devising approximate Riemann solvers, though these are certainly not the only approaches: linearized solvers and two-wave solvers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notation and structure of approximate solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In both of the approaches described below, the approximate Riemann solution consists entirely of traveling discontinuities.  Following <cite data-cite=\"fvmhp\"><a href=\"riemann.html#fvmhp\">(LeVeque, 2002)</a></cite>, we refer to these traveling discontinuities as *waves*, and denote them by $\\wave^p$, where the index $p$ denotes the characteristic family and typically ranges from $1$ to $m$ for a system of $m$ equations.  For each wave, the approximate solver must also give a wave speed $s^p$.\n",
    "\n",
    "The net effect of each wave from the Riemann solution is given by the product of the wave and its speed.  In a finite volume scheme, the rate of change of the cell average to the left of a given interface is given by  \n",
    "$$\\amdq = \\sum_{p=1}^m (s^p)^- \\wave^p$$  \n",
    "and that to the right is given by  \n",
    "$$\\apdq = \\sum_{p=1}^m (s^p)^+ \\wave^p$$  \n",
    "where $(x)^- = \\min(x,0)$ and $(x)^+ = \\max(x,0)$.  We refer to $\\amdq, \\apdq$ as *fluctuations*.\n",
    "\n",
    "The purpose of an approximate Riemann solver, in this context, is to determine the waves $\\wave^p$ and speeds $s^p$; these can then be used to update the numerical solution via the fluctuations.\n",
    "\n",
    "A common, but different, viewpoint is that the Riemann solver must produce an approximation of the flux at $x=0$.  This can be used to update the numerical solution via a *flux-differencing* scheme. (*add more on the relation between fluctuations and fluxes*)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linearized Riemann solvers \n",
    "Consider a nonlinear system $q_t + f(q)_x = 0$. If $q_l$ and $q_r$ are close to each other, as is often the case over smooth regions of a more general solution, then the nonlinear system can be approximated by a linear problem of the form $q_t + \\hat A q_x = 0$.  The coefficient matrix $\\hat A$ should be some approximation to  $f'(q_l) \\approx f'(q_r)$ in the case where $\\|q_l-q_r\\|$ is small.  The idea of a general linearized Riemann solver is to define a matrix $\\hat A(q_l, q_r)$ that has this property but also makes sense as an approximation in the case when $\\|q_l-q_r\\|$ is not small.  For many nonlinear systems there is a *Roe linearization*, a particular function that works works very well based on ideas introduced originally by <NAME> <cite data-cite=\"Roe1981\"><a href=\"riemann.html#Roe1981\">(Roe, 1981)</a></cite>.  For systems such as the shallow water equations or the Euler equations, there are closed-form expressions for the eigenvalues and eigenvectors of $\\hat A$ and the solution of the linearized Riemann problem, leading to efficient solvers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Two-wave solvers \n",
    "Since the Riemann solution impacts the overall numerical solution only based on how it modifies the two neighboring solution values, it seems reasonable to consider approximations in which only a single wave propagates in each direction.  The solution will have a single intermediate state $q_m$ such that $\\wave_1 = q_m - q_l$ and $\\wave_2 = q_r-q_m$.  There are apparently $m+2$ values to be determined: the middle state $q_m$ and the speeds $s_1, s_2$.  In order for the method to be conservative, it must satisfy the $m$ conditions  \n",
    "\\begin{align}\n",
    "f(q_r) - f(q_l) = s_1 \\wave_1 + s_2 \\wave_2.\n",
    "\\end{align}  \n",
    "This can be solved for the middle state to find  \n",
    "\\begin{align}  \\label{AS:middle_state}\n",
    "q_m = \\frac{f(q_r) - f(q_l) - s_2 q_r + s_1 q_l}{s_1 - s_2}.\n",
    "\\end{align}  \n",
    "It remains only to specify the wave speeds, and it is in this specification that the various two-wave solvers differ.  In the following sections we briefly discuss the choice of wave speed for a scalar problem; the choice for systems will be elaborated in subsequent chapters.\n",
    "\n",
    "In addition to the names and references provided below, let us mention that this class of solvers is an ingredient in the so-called *central schemes*.  Due to the extreme simplicity of two-wave solvers, the resulting central schemes are often even referred to as being \"Riemann-solver-free\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lax-Friedrichs (LF) and local-Lax-Friedrichs (LLF)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The simplest such solver is the *Lax-Friedrichs* method, in which it is assumed that both waves have the same speed:\n",
    "$$-s_1 = s_2 = a,$$\n",
    "where $a\\ge 0$.  Then \\label{AS:middle_state} becomes\n",
    "$$q_m = -\\frac{f(q_r) - f(q_l)}{2a} + \\frac{q_r + q_l}{2}.$$\n",
    "In the original Lax-Friedrichs method, the wave speed $a$ is taken to be the same in every Riemann problem over the entire grid; in the local Lax Friedrichs method, a different speed $a$ may be chosen for each Riemann problem.\n",
    "\n",
    "For stability reasons, the wave speed should be chosen at least as large as the fastest wave speed appearing in the true Riemann solution.  However, choosing a wave speed that is too large leads to diffusion.  For the LLF method (originally due to Rusanov), the wave speed is chosen as\n",
    "$$a(q_r, q_l) = \\max(|f'(q)|)$$  \n",
    "where the maximum is taken over all values of $q$ between $q_r$ and $q_l$.  This ensures stability, but may introduce substantial damping of slower waves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <NAME> (HLL)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A less dissipative solver can be obtained by allowing the left- and right-going waves to have different speeds.\n",
    "This approach was developed in <cite data-cite=\"HLL\"><a href=\"riemann.html#HLL\">(<NAME>)</a></cite>.  The solution is then determined by \\eqref{AS:middle_state}.  In the original HLL solver, it was suggested to again to use speeds that bound the possible speeds occurring in the true solution.  For a scalar problem, this translates to  \n",
    "\\begin{align*}\n",
    "s_1 & = \\min(f'(q)) \\\\\n",
    "s_2 & = \\max(f'(q)),\n",
    "\\end{align*}  \n",
    "where again the minimum and maximum are taken over all values between $q_r$ and $q_l$.  Many refinements of this choice have been proposed in the context of systems of equations.  Again, these will be discussed in later chapters."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
{'fraction_non_alphanumeric': 0.0963413977046177, 'fraction_numerical': 0.005334339134651651, 'mean_word_length': 3.657465495608532, 'pattern_counts': {'":': 70, '<': 38, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '206704', 'n_tokens_mistral': 5317, 'n_tokens_neox': 4949, 'n_words': 2621}