270E Lecture Summaries

December 5, 2008 (last lecture)

• Steps involved in constructing solution procedures for the incompressible Euler or Navier-Stokes equations (review)
• Alternate discretizations
  • finite difference
    • non-uniform mesh
    • overlapping grids
    • composite grids
    • cut-out grids/embedded object methods
  • finite elements
  • spectral methods
  • particle methods
• Spectral methods

December 3, 2008

• Summary of timestepping for projection methods
  • High order explicit: apply high order explicit methods directly to the projection form of the equations
  • First order implicit: $\vec u^n = \mathcal{P}($ implicit step of equations without $\nabla {\rm P})$
  • High order implicit: See literature. Timestepping and projection step typically intertwined.
• Solving problems in infinite domains, continued.
  • Sketch of ideas for ${\rm R}^2$ and an infinite tube.

December 1, 2008

• Implicit timestepping for the Stokes equations continued.
  • review of the classic projection (fractional step) procedure
  • comparing the matrix exponential of the true solution to the matrix exponential approximation created by the projection method
  • why the classic projection procedure is only first order accurate
  • comments about procedures for obtaining higher order accuracy in time for implicit methods.
• Solving problems in infinite domains
  • two sample problems: (a) evolution of a vortex patch in ${\rm R}^2$ and (b) flow over a back step in a tube of infinite extent.
  • complications introduced by the infinite domain aspect of the problem
  • computing the solution of Poisson's equation for an infinite domain--- intuitively why it's possible

November 26, 2008

• Stokes equations (approximation to Navier-Stokes when viscosity is large, or equivalently, when the Reynolds number, Re is small).
• The general projection procedure for the Stokes equations
  • explicit timestepping schemes
  • the need for implicit timestepping schemes
• Implicit timestepping projection procedures
  • classical projection procedure (fractional step derivation)
    • advance the solution of equations without regard to pressure for $dt$ using an implicit timestpping method
    • apply the projection operator

November 24, 2008

• The computation of the discrete projection operator continued.
  • Warning about iterative procedures for solving for the gradient component (watch out for null spaces!)
• The computation of the discrete projection operator on a MAC grid using a discrete approximation to Method #2, the stream function vorticity approach
  • verification of discrete vector identities required for success
    • velocities computed from differences of the discrete stream function are discretely divergence free
    • the discrete curl of the discrete gradient vanishes
  • formulation of the equations for the discrete stream function
  • boundary conditions for the discrete stream function
  • relation between the equations for the discrete stream function and the standard discretization of the Laplace operator with a five-point difference stencil and Dirichlet boundary conditions (they're equal).

November 21, 2008

• The computation of the projection operator continued.
  • The block matrix form of the discrete projection equations
  • The computation of the discrete projection operator on a MAC grid using a discrete approximation to Method #1, the "gradient" method.
    • construction of the equations for the gradient component (pressure)
      • the divergence equations and the necessity for separating equation components involving boundary values (known) and interior values (unknown)
      • substitution of the discrete Hodge decomposition relation into the divergence equations
      • identification of the equations determining the gradient component.
      • the relation between the equations for the gradient component and that of a standard discretization of the Laplace equations with a five-point difference stencil and Neumann boundary conditions (they are not equal).

November 19, 2008

• Solving the Navier-Stokes equations in $(\vec u, {\rm P})$ formulation
  • The general strategy for an explicit timestep projection method
  • Alternate approximation of the Laplace operator for velocity components at grid points adjacent to the boundaries of the domain.
• The computation of the projection operator
  • The underlying linear algebra problem

November 17, 2008

• Implementation details for solving the Euler equations in $(\vec u, {\rm P})$ formulation cont.
  • Approximation of the convection term
  • Time stepping -- implementing RK4
  • Alternate approximations for the convection term; the idea behind 6.2.7(b) in Peyret and Taylor.

November 14, 2008

• Implementation details for solving the Euler equations in $(\vec u, {\rm P})$ formulation
  • Staggered grids
  • The discrete projection operator
  • Approximation of the convection term

November 12, 2008

• Solving the Euler equations in $(\vec u, {\rm P})$ formulation
  • The idea behind projection methods
  • The Helmholtz-Hodge decomposition $\vec z = \vec w + \nabla \phi$
  • Helmholtz-Hodge decomposition
    • Method #1: gradient procedure
    • Method #2: stream function procedure

November 10, 2008

• Continued with a discussion of the procedure for determining the boundary vorticity
• Presented a "big picture" description of the boundary vorticity problem
  • We're solving a differential equation with a differential constraint. When spatial discretizations are employed this leads to a system of differential-algebraic equations (DAE's), thus the procedures developed for handling the problem of boundary vorticity specification can be interpreted as the application of procedures for general DAE's.
    
  • Thom's boundary condition can be viewed as the application of the DAE procedure where one approximately solves the constraint equations to determine the un-specified components in the differential equation.
  • Other procedures:.
    • Implicit timestepping procedure used for DAE's
    • Differentiating the constraint leads to "boundary vorticity creation" procedures.
    • Projection methods.

November 7, 2008

• Discussed the problem of using conserved quantities to estimate rates of convergence --- explaining the peculiar convergence results seen for Assignment 6.
• Derived the vorticity stream function form of the Navier-Stokes equations
• Discussed the problem with vorticity boundary conditions, and the origin of Thom's procedure for determining the boundary vorticity.

November 5, 2008

• Continued with a discussion of the velocity field and motion of point vortices; the motion of a point vortex near a wall.
• Discussed the incompressible Navier-Stokes equations:
  
  • The physics that gets left out in when using the Euler equations for an ideal incompressible fluid
  • Described the stress-tensor for an incompressible Newtonian fluid
  • Used the control volume approach to derive the Navier-Stokes equations

November 3, 2008

• Discussed the procedure for estimating convergence rates when an exact solution is not available.
• Described the velocity field due to a point vortex.
• Described how one can use ones intuitive understanding of the motion of a point vortex approximation to obtain and idea about what the fluid flow should look like.

October 31, 2008

• Derived the vorticity-stream function formulation of the Euler equations.
• Discussed implementation details
  • code components for solution of the vorticity stream-function equations
  • required modifications of time-stepping procedure
  • treatment of boundary vorticity

October 29, 2008

• Derived the Euler equations for an incompressible fluid of constant density

October 27, 2008

• Information about FFTW3
  • performance dependence on N
  • why FFTinterface classes were created
  • possible extensions
• Homework 3 and 4 (results now posted)
• Understanding the behavior of finite difference method solutions via the "modified equation" approach

October 24, 2008

Creation of a Fast Poisson solver (continued)

• Fourier method for 1D problem
• discrete analog of the Fourier method for 1D problem
• computational ingredients
  • determination of the discrete transform factors
  • forward and inverse discrete sin transform
  • formulas and use of FFTW3 = fast Fourier transform library
• remarks on code structure (example code in class repository)
• comments on extending approach to 2D

October 22, 2008

Creation of a Fast Poisson solver

• standard procedure for 1D problem
  • discrete equations
  • implementation details
• extension of standard procedure for 2D problem
  • discrete equations
  • implementation details (idea behind HWSCRT's calling convention)
  • why we seek an alternative procedure
    
• alternate procedure for 1D problem (one that we can readily generalize to 2D)
  • Fourier method (sin series solution)
  • discrete analog of the Fourier method

October 20, 2008

Further discussion of the stream function its' use for determining divergence free vector fields with specified velocities on the boundary of a computational domain. Also discussed how information concerning the velocity field can be can extracted from a contour plot of the stream function.

Discussed aspects of the routine FastPoissonSolverDirichlet; the general idea behind the routine and the routines use of the NCAR FishPack routine HWSCRT.

October 17, 2008

Discussed the relation of timestep restriction associated with the CFL condition and the timestep restriction associated with the stability of the numerical method.

Began discussion of the use of a stream function to determine divergence free vector fields and described the procedure to be used to obtain a velocity field from a stream function that is determined numerically.

October 15, 2008

Discussed the error bound for the solution procedures:

• the leading terms of the error bound consist of two terms, one associated with the ODE discretization error and the other associated with the spatial discretization error
• the stability condition for the methods can be expressed as a condition on the eigenvalues of the spatial discretization operator and the regions of absolute stability for the ODE methods
  

Presented the results of a local truncation error analysis of the spatial discretizations used.

Presented the results of the computation of the eigenvalues of the spatial discretizaton operators. The basis for these computations is discrete Fourier analysis

Went through the process of determining the stability condition when RK methods of order one through four are used. This process consists of combining knowledge of the eigenvalues of the spatial discretization operator and the region of absolute stability for the methods.

October 13, 2008

Stated and the sketched the derivation of an error bound for solution procedures based upon method of lines discretizations.

October 10, 2008

Disucssed

• estimated rates of convergence
• why methods (b) and (c) yield identical results (an artifact of the test case being used)
• why method (c) is clever (the method preserves the discrete L2 norm of the soluiton)

• derivation of an error bound; theory to help answer questions about choosing the relation between the time-step and the spatial step as well as the order of the ODE method
• use of the modified equation perspective to understand the qualitative features of the solutions created with different methods

Presented the notation to be used in the derivation of the error bound.

October 8, 2008

Continued with the discussion of Assignment 2 C++ implementation
Discussed use of container classes for parameters and an array class for solution values
Considered the following questions/complaints wirh regard to assigment 2

Q1: I'm getting peculiar converence results --- why?
C1: I didn't like having to write down so much to carry out the experiments
Q2: Method (b) and (c) yield exactly the same results -- does this mean there is a bug in the code?
Q4: Why is method (b) a clever method?
Q5: What was responsible for the variation of the methods behavior when Runge-Kutta methods were changed. In particular, for a given RK ODE order, why did some of the schemes work statisifactorily, but others "blew up".
Q6: The results at one rotation weren't very satisfactory --- does this mean there is a bug in the code? If it isn't a bug, then what is causing the results to appear as they do?

Answered Q1, and for C1, suggested that to avoid having to write so much, one can have the computer carry out and tabulate the experiments. There is no need for a script to do this, one can modify the loops within the main routine.

Showed animations of some sample solutions obtained with each method.

October 6, 2008

Described the test problem used in assignment 2 and it's exact solution.
Described the Runge-Kutta methods used in assignment2.
Discussed the general implementation strategy for the method of lines procedure.
Discussed the reasons for not using a standard matrix/vector approach, even though the system of ODE's being solved is a linear system of ODE's.
Began a discussion of the C++ specific constructs used in the implementation --- container classes for the method parameters and an array class, DoubleArray2D, to represent solution values at the grid nodes.

October 3, 2008

Described the origin of the four numerical methods being studied in Assignment 2. The first two are simple methods, often the first methods that are implemented when one's aim is to just create a functional program.The second two methods the result of trying to be "clever".

1. Non-conservation form, $\dfrac{\partial {\rm S}}{\partial t} \, = -\vec{u} \, \, \nabla {\rm S}$, with standard second order centered differences used to approximate the derivatives in $ \nabla {\rm S}$.
2. Non-conservation form, $\dfrac{\partial {\rm S}}{\partial t} \, = -\vec{u} \, \, \nabla {\rm S}$, with "upwind", first order differences used to approximate the derivatives in $ \nabla {\rm S}$.
3. Mixed conservation and non-conservation form, $\dfrac{\partial {\rm S}}{\partial t} \, = -\dfrac{1}{2} \vec{u} \, \, \nabla {\rm S} -\dfrac{1}{2} {\rm div} (\vec{u}{\rm S})$ with standard second order centered differences used to approximate derivatives. Question: Why is this a "clever" thing to do?
4. Conservation form, $\dfrac{\partial {\rm S}}{\partial t} \, =-{\rm div} (\vec{u}{\rm S})$. A finite volume discretization where the integral of the convective flux over the cell boundary is approximated using Simpson's rule, and a midpoint rule is used to approximate the integral of the time derivative.

Warning: In the code distributed for assignment 2, the spatial discretization approximations are implemented using a specification of S at all points of the boundary. This is not a correct specification of the boundary conditions; however, the consequences of this flaw will not be observed with the test cases being run for the assignment. This flaw will be "fixed" in assignment 3.

October 1, 2008

Derived the equation for convective transport :

• express conservation of convected quantity in a specified region
• apply the divergence theorem

Indicated the origin of the expression used for the convective flux
Defined conservation form and non-conservation form for the transport equation.
Discussed how constant density and conservation of mass imply incompressibility, but incompressibility does not imply constant density, e.g. one can have incompressible flows for fluids of variable density.
Outlined the setup for the numerical approximation of the equation for convective transport --- a "Method of Lines" approach is being used.
Began a derivation of a control volume discretization for spatial derivatives. This method is the first of four numerical methods whose approximation properties will be explored in assignment 2.

September 29, 2008

• The downloading the assignment files into the course directory structure from the web repository.
• The creation of a solution/project using Visual Studio, adding files to the project and setting include paths, and then building and running the program.
• The building of the sample executable under a Linux/Unix shell.
• The use of GNUplot to create surface and contour plots of the output.

Began the derivation of an equation for passive transport of a scalar quantity by a fluid with a prescribed velocity (e.g. convection).

September 26, 2008

Business: see Course Policies

Scientific computing is a synthesis of knowledge of

• algorithms/numerical procedures
• mathematics
• techniques and tools for computational implementation
  

• knowledge of a particular problem area
  

Our focus is on scientific computing where the problem area is incompressible fluid flow (a type of fluid motion).

What defines a fluid motion.
Fluids include both liquids and gasses.
Most computational methods focus on computing the velocity of the fluid.
The assumption of incompressibility is made so we can ignore sound waves as part of a fluid motion.
Target equations are the Navier-Stokes equations.

Q1: Where do the equations come from?
Q2: How are we going to develop numerical methods to solve them?

A1: As the course progresses, the equations will be derived (slowly).
A2: The NS equations are a combination of equations of hyperbolic, parabolic and elliptic. We well be combining numerical standard numerical methods for equations of these types to create the solution procedures for the NS equations.

Topics (each will have a corresponding assignment)

2D Convection by a specified divergence free velocity field.
2D Convection-Diffusion by a specified divergence free velocity field.
Time independent vortical flows (construction of divergence free vector fields that correspond to time-independent rotational flow).
FFT's, construction of fast Poisson solvers
Euler equations using the vorticity-stream function formulation
Navier-Stokes equations using the vorticity-stream function formulation
Euler equations using primitive (u,P) variables.
Navier-Stokes equations using primitive (u,P) variables.