Full HTML for

Scripted foilset CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation

Given by Geoffrey C. Fox at Delivered Lectures of CPS615 Basic Simulation Track for Computational Science on 8 November 96. Foils prepared 11 November 1996
Outside Index Summary of Material

This starts basic module on Partial Differential Solvers with
Introduction to Classification of Equations
Basic Discretization
Derivation of Sparse Matrix Formulation
Analogies of Iteration with Artificial Time
Start of Explicit Matrix Formulation for Simple Cases

Table of Contents for full HTML of CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
Indicates Available audio which is lightpurpleed out if missing
1 Delivered Lectures for CPS615 -- Base Course for the Simulation Track of Computational Science
Fall Semester 1996 --
Lecture of November 8 - 1996
2 Abstract of Nov 8 1996 CPS615 Lecture
3 Abstract of PDE and Iterative Solver CPS615 Module
4 Partial Differential Equations: Use in Continuum Physics
Examples and basic Notation
5 Examples of Different Types of Partial Differential Equations:
The Wave Equation (Hyperbolic) and Typical One Dimensional Solution
6 Examples of Different Types of Partial Differential Equations:
The Parabolic Equation
7 Examples of Different Types of PDE's: Laplace and Poisson Elliptic Equations
8 What Conditions are sufficient for solution of PDE's -- Cauchy Boundary Conditions and Hyperbolic,Parabolic and Elliptic PDE's
9 Closed Boundaries; Dirichlet and Neumann Conditions
Summary of what PDE Types have What Boundary Conditions
10 Examples of Open(Diffusion) and Closed(Laplace) Boundary Conditions
11 Solutions to Elliptic Equations by Finite Differences
12 Central Difference Operator with error O(h2)
13 Difference Equation form of the Operator to solve Laplace's equation
14 The 12 by 12 Block Tridiagonal Equations Coming from Laplace's Equation on a Tiny 5 by 6 Grid
15 General Form of Sparse Matrix Coming from Laplace's Equation - I
16 General Form of Sparse Matrix Coming from Laplace's Equation in two dimensions - II
17 Iterative Methods and Analogy to Diffusion with an Artificial Time
18 Solution of Artificial Time Equation as a Diffusion System Discretized in Space and Time
19 General 2D Artificial Time Diffusion Equation in Iterative Form
20 Traditional Iterative Methods as Special Cases of Artificial Time Diffusion Formalism
21 Simple Iterative Methods: Jacobi, Gauss-Seidel, SOR
22 Matrix Notation for Iterative Methods

Outside Index Summary of Material

HTML version of Scripted Foils prepared 11 November 1996

Foil 1 Delivered Lectures for CPS615 -- Base Course for the Simulation Track of Computational Science
Fall Semester 1996 --
Lecture of November 8 - 1996

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index
Geoffrey Fox
NPAC
Room 3-131 CST
111 College Place
Syracuse NY 13244-4100
HTML version of Scripted Foils prepared 11 November 1996

Foil 2 Abstract of Nov 8 1996 CPS615 Lecture

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index
This starts basic module on Partial Differential Solvers with
Introduction to Classification of Equations
Basic Discretization
Derivation of Sparse Matrix Formulation
Analogies of Iteration with Artificial Time
Start of Explicit Matrix Formulation for Simple Cases
HTML version of Scripted Foils prepared 11 November 1996

Foil 3 Abstract of PDE and Iterative Solver CPS615 Module

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 33.1
This Introduces the three fundamental types of PDE's -- Elliptic, Parabolic and Hyperbolic and studies the numerical solution of Elliptic Equations
The sparse matrix formulation is used and iterative approachs -- Jacobi, Gauss Seidel and SOR are defined
These are motivated by analogies between equilibrium of diffusive equations and elliptic systems
Eigenvalue analysis is used to discuss convergence of methods
HTML version of Scripted Foils prepared 11 November 1996

Foil 4 Partial Differential Equations: Use in Continuum Physics
Examples and basic Notation

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 177.1
Physical systems which behave as continuous systems at a macroscopic level, in a fluid fashion
Examples:
  • airflow over an airplane wing
  • radar waves reflecting from airport traffic
  • blood circulation in the human body
  • simulating global climate to predict changes in the ozone layer
Partial Differential Equations (PDE's) are characterized by rate of changes in 2 or more independent variables
HTML version of Scripted Foils prepared 11 November 1996

Foil 5 Examples of Different Types of Partial Differential Equations:
The Wave Equation (Hyperbolic) and Typical One Dimensional Solution

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 264.9
Wave equation (hyperbolic): One dimensional equation is:
The natural generalization is Maxwell's Equations describing computational Electromagnetics for radar cross-sections of aircraft and antenna patterns
Numerical Relativity has interesting complex wave equation in three dimensions.
HTML version of Scripted Foils prepared 11 November 1996

Foil 6 Examples of Different Types of Partial Differential Equations:
The Parabolic Equation

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 92.1
This is a heat or other type of diffusion equation lying intermediate between elliptic and hyperbolic equations
where y is temperature
  • k = K/Cr is the rate of heat diffusion
  • and K is thermal conductivity
  • C is specific heat
  • r is the density
HTML version of Scripted Foils prepared 11 November 1996

Foil 7 Examples of Different Types of PDE's: Laplace and Poisson Elliptic Equations

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 128.1
Laplace's equation (elliptic): steady state in systems of electric or magnetic fields in a vacuum or the steady flow of incompressible non-viscous fluids
Poisson's equation (elliptic): a variation of Laplace when an outside force, given by the function f, is applied to the system
HTML version of Scripted Foils prepared 11 November 1996

Foil 8 What Conditions are sufficient for solution of PDE's -- Cauchy Boundary Conditions and Hyperbolic,Parabolic and Elliptic PDE's

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 288
Cauchy conditions
y and ¶y/¶n are given
on a curve
Solution given by Taylor series for each point near curve if these are sufficient to determine higher derivatives
  • Consider general form of PDE:
Can be solved as linear system with deterministic equations for derivatives of boundary conditions if coefficients have certain characteristics -- Gives rise to three types:
  • b2>4ac hyperbolic equations -- Above strategy works
  • b2=4ac parabolic equations
  • b2<4ac elliptic equations
HTML version of Scripted Foils prepared 11 November 1996

Foil 9 Closed Boundaries; Dirichlet and Neumann Conditions
Summary of what PDE Types have What Boundary Conditions

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 408.9
Another problem with Cauchy conditions on closed boundary
Two other types of boundary conditions
  • Dirichlet Boundary Conditions: y is specified at every point of C
  • Neumann Boundary Conditions: ¶y/¶n is specified at every point of C
Boundary conditions to give solutions for types of equations
Equation Type -- Boundary Curve -- Boundary Data -- Example
Hyperbolic Open Cauchy Wave Equation
Parabolic Open Dirichilet or Neumann Diffusion Equation
Elliptic Closed Dirichilet or Neumann Laplace's Equation
HTML version of Scripted Foils prepared 11 November 1996

Foil 10 Examples of Open(Diffusion) and Closed(Laplace) Boundary Conditions

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 264.9
Example of 2nd order diffusion equation with open boundary curve
Example of Laplace's equation with closed boundary curve
HTML version of Scripted Foils prepared 11 November 1996

Foil 11 Solutions to Elliptic Equations by Finite Differences

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 228.9
Discretize region by imposing grid points with spacing h
Represent two adjacent neighbors of the point (x,y) in the x direction by Taylor series
Add the two equations
HTML version of Scripted Foils prepared 11 November 1996

Foil 12 Central Difference Operator with error O(h2)

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 247.6
Solve previous equation for 2nd derivative
Combine with similar equation in y direction
Backward difference operator and forward difference operator are O(h)
Higher order operators use more points on the grid (larger stencil) and are more accurate
HTML version of Scripted Foils prepared 11 November 1996

Foil 13 Difference Equation form of the Operator to solve Laplace's equation

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 167
Use difference operator
to solve for every
interior point of grid
Nx*Ny linear
equations
of the form
HTML version of Scripted Foils prepared 11 November 1996

Foil 14 The 12 by 12 Block Tridiagonal Equations Coming from Laplace's Equation on a Tiny 5 by 6 Grid

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 388.8
Example equations
to solve Laplace on
a 5x6 grid with b
labelling boundary
and y internal points
System of 12 equations - block tridiagonal
HTML version of Scripted Foils prepared 11 November 1996

Foil 15 General Form of Sparse Matrix Coming from Laplace's Equation - I

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 84.9
HTML version of Scripted Foils prepared 11 November 1996

Foil 16 General Form of Sparse Matrix Coming from Laplace's Equation in two dimensions - II

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 492.4
A sparse matrix
with two bands --
one next to diagonal
and the other a
"distance" Nx
away
Note original grid shown here is Nx by Ny but matrix is Nx Ny by Nx Nywithzeros outside a band of total width 2Nx +1
Note no "compact labelling" where points near each other in two dimensions remain near each in one dimension after mapping onto vector (one dimension)
HTML version of Scripted Foils prepared 11 November 1996

Foil 17 Iterative Methods and Analogy to Diffusion with an Artificial Time

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 457.9
We must use Iterative methods to solve the linear equations coming from solution of large elliptic equations (Laplace's equation in example we will study)
We can motivate iteration by studying an "artificial" diffusion equation
subject to y having same boundary conditions (in x for all "artificial time" t ) as original equation
that we needed to solve
Consider ANY trial function y = y(0) at t = 0
Then we solve (*) and look at converged solution as t
As
The iteration of (*) in t gives a solution of (**) in limit of infinite t
HTML version of Scripted Foils prepared 11 November 1996

Foil 18 Solution of Artificial Time Equation as a Diffusion System Discretized in Space and Time

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 138.2
If we solve the diffusion equation (*) by finite difference in space (which is as for Laplace's equation) and time
Here "t" could be t,t+dt or an average such as:
t0 is Initial value which we can take as t=0
t1 = t0+ dt .....
tk+1=tk+dt
The iteration gives yk(x)=y(x,tk) in terms of y(k-1)(x)
HTML version of Scripted Foils prepared 11 November 1996

Foil 19 General 2D Artificial Time Diffusion Equation in Iterative Form

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 131
This give Iterative equation if we use k to label time steps
c1 yk+1(x,y) = ( y"k"(x+h,y) + y"k"(x-h,y)+y"k"(x,y+h)+y"k"(x,y-h))/4
- c2 y"k"(x,y)
where c1 + c2 = 1
and the value of c1,c2 depend on K,h and dt.
as dt is arbitary, we can choose c1
(and hence c2 = 1 - c1 ) to optimize convergence.
We use cryptic notaation "k" to repreprent various possible choices for evaluating time on right hand side. Simplest is "k" = k but choices are k, k+1 or linear combinations which can vary for different x values.
HTML version of Scripted Foils prepared 11 November 1996

Foil 20 Traditional Iterative Methods as Special Cases of Artificial Time Diffusion Formalism

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 61.9
Different Choices of c1, c2, "k" give
Either Jacobi Iterative Method
  • This is "k" = k
    • c1 = 1
    • c2 = 0
or Gauss Seidel
  • This is gotten with a particular choice of "k" as sometimes k and sometimes k+1
    • c1 = 1
    • c2 = 0
Over relaxation
  • Choose suitable c2 as nonzero value
HTML version of Scripted Foils prepared 11 November 1996

Foil 21 Simple Iterative Methods: Jacobi, Gauss-Seidel, SOR

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 146.8
There are many iterative methods - our diffusion equation analogy suggested the three simplest or stationary methods - so called because iteration equation is the same at each iteration
Jacobi Method The Jacobi method is based on solving for every variable locally with respect to the other variables; one iteration of the method corresponds to solving for every variable once. The resulting method is easy to understand and implement, but convergence is slow.
Gauss-Seidel The Gauss-Seidel method is like the Jacobi method, except that it uses updated values as soon as they are available. In general, it will converge faster than the Jacobi method, though still relatively slowly.
Successive Overrelaxation (SOR) Successive Overrelaxation (SOR) can be derived from the Gauss-Seidel method by introducing an extrapolation parameter w. For the optimal choice of w, SOR converges faster than Gauss-Seidel by an order of magnitude.
HTML version of Scripted Foils prepared 11 November 1996

Foil 22 Matrix Notation for Iterative Methods

From CPS615-Basic PDE Solver Discussion and Sparse Matrix Formulation Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 8 November 96. *
Full HTML Index Secs 558.7
Superfix k denotes iteration
Write A = D-L-U D = Diagonal L = Lower Triangle U = Upper Triangle
© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Fri Aug 15 1997