Full HTML for

Scripted foilset CPS615 Module on Iterative PDE Solvers

Given by Geoffrey C. Fox at CPS615 Basic Simulation Track for Computational Science on Fall Semester 95. Foils prepared 8 November 1995
Outside Index Summary of Material

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

Table of Contents for full HTML of CPS615 Module on Iterative PDE Solvers

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
Denote Foils where Image is not available
1 Iterative Solver Module
CPS 615 -- Computational Science in
Simulation Track
Solution of Simple Partial Differential Equations and Iterative Solvers
Fall Semester 1995
2 Abstract of PDE and Iterative Solver CPS615 Module
3 Partial Differential Equations: Use in Continuum Physics
Examples and basic Notation
4 Examples of Different Types of Partial Differential Equations:
The Wave Equation (Hyperbolic) and Typical One Dimensional Solution
5 Examples of Different Types of Partial Differential Equations:
The Parabolic Equation
6 Examples of Different Types of PDE's: Laplace and Poisson Elliptic Equations
7 What Conditions are sufficient for solution of PDE's -- Cauchy Boundary Conditions and Hyperbolic,Parabolic and Elliptic PDE's
8 Closed Boundaries; Dirichlet and Neumann Conditions
Summary of what PDE Types have What Boundary Conditions
9 Examples of Open(Diffusion) and Closed(Laplace) Boundary Conditions
10 Solutions to Elliptic Equations by Finite Differences
11 Central Difference Operator with error O(h2)
12 Difference Equation form of the Operator to solve Laplace's equation
13 The 12 by 12 Block Tridiagonal Equations Coming from Laplace's Equation on a Tiny 5 by 6 Grid
14 General Form of Sparse Matrix Coming from Laplace's Equation - I
15 General Form of Sparse Matrix Coming from Laplace's Equation in two dimensions - II
16 Iterative Methods and Analogy to Diffusion with an Artificial Time
17 Solution of Artificial Time Equation as a Diffusion System Discretized in Space and Time
18 General 2D Artificial Time Diffusion Equation in Iterative Form
19 Traditional Iterative Methods as Special Cases of Artificial Time Diffusion Formalism
20 Simple Iterative Methods: Jacobi, Gauss-Seidel, SOR
21 Matrix Notation for Iterative Methods
22 General Iteration Matrix Splitting and Preconditioning
23 Explicit Form of General Jacobi Iteration
in Matrix and Component Formalism
24 The Special Case of Jacobi Iteration for Laplace's Equation
25 Pseudo Code for the Jacobi Method
26 Formalism for Convergence of Stationary Iterative Methods
27 Eigenvalue Analysis of Iterative Methods
28 Estimation of largest Eigenvalue in One Dimension
29 Eigenvalues and Convergence Rate of Jacobi Iteration
30 Difficult and Easy Eigenfunctions Controlling
Convergence of Jacobi Iteration
31 Decoupling of Even and Odd Grid Point Updates in Basic Jacobi Iteration
32 Damping of Eigenfunctions of Short and Long Wavelength
33 Extension of Jacobi Eigenvalue Analysis to two or more Dimensions
34 Direct Solution Method for Ax=b
35 Banded Matrix Computational Complexity
36 Comparison of Computational Complexity between Direct and Iterative Methods
37 Memory Use in Direct and Iterative Methods
38 Over Relaxation (SOR) and Relation to Jacobi and Gauss-Seidel
39 Over Relaxation Eigenvalues and Matrices for Jacobi Iteration
40 Jacobi Iteration Eigenvalues as a function of Over Relaxation Parameter
41 Jacobi Relaxation for Over Relaxation Parameter w =1/2
42 Introduction to Gauss-Seidel Iterative Approach
43 6:Mathematical and Pseudo Code Form of Gauss Seidel Iteration Method
44 7:Mathematical (Matrix) Form of Gauss Seidel
45 8:Parallelism in Gauss-Seidel Iteration
46 9:Matrix Example Stencil
47 10:Matrix---Wavefront Parallelism for Gauss Seidel
48 11:The Red-Black Two Phase Parallel Gauss Seidel Iteration
49 12:Analysis of Parallel Red Black Gauss Seidel
50 13:Eigenvalues of Gauss Seidel Iteration Matrix
51 14:Comparison of Convergence of Gauss-Seidel and Jacobi Iteration
52 15:Successive Overrelaxation Iteration Method (SOR)
53 16:Convergence of SOR Compared to Jacobi and Gauss Seidel
54 17:Estimate of Over Relaxation Parameter
55 18:Pseudo Code for SOR---Successive Over Relaxation

Outside Index Summary of Material

HTML version of Scripted Foils prepared 8 November 1995

Foil 1 Iterative Solver Module
CPS 615 -- Computational Science in
Simulation Track
Solution of Simple Partial Differential Equations and Iterative Solvers
Fall Semester 1995

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Geoffrey Fox
NPAC
Syracuse University
111 College Place
Syracuse NY 13244-4100
HTML version of Scripted Foils prepared 8 November 1995

Foil 2 Abstract of PDE and Iterative Solver CPS615 Module

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

Foil 10 Solutions to Elliptic Equations by Finite Differences

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

Foil 11 Central Difference Operator with error O(h2)

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Use difference operator
to solve for every
interior point of grid
Nx*Ny linear
equations
of the form
HTML version of Scripted Foils prepared 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Scripted Foils prepared 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

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

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
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 8 November 1995

Foil 21 Matrix Notation for Iterative Methods

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Superfix k denotes iteration
Write A = D-L-U D = Diagonal L = Lower Triangle U = Upper Triangle
HTML version of Scripted Foils prepared 8 November 1995

Foil 22 General Iteration Matrix Splitting and Preconditioning

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Generic Iteration
  • Split A = M-N Ax = b implies Mx = Nx + b So write Mxk = Nx(k-1) + b
  • All iteration methods have this form for different choices of M, N, A and b
    • One can change A and b by preconditioning
    • M1-1AM2-1M2x =M1-1 b is same equation as before for any choice of matrices M1 and M2
  • All these choices are designed to accelerate convergence of iterative methods
HTML version of Scripted Foils prepared 8 November 1995

Foil 23 Explicit Form of General Jacobi Iteration
in Matrix and Component Formalism

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Scripted Foils prepared 8 November 1995

Foil 24 The Special Case of Jacobi Iteration for Laplace's Equation

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Scripted Foils prepared 8 November 1995

Foil 25 Pseudo Code for the Jacobi Method

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Choose an Initial Guess x(0) to the solution x.
for k = 1,2, ......
  • for i = 1,2,...,n
  • s = 0
  • for j = 1,2, ... ,i-1,i+1,...,n
    • s = s + a i,j x j (k-1)
  • end
  • xi(k) = (bi - s)/a i,i
  • end
Check Convergence -- continue loop over k if required (e.g. maximum (over i) change |xi(k) -xi(k-1) | is too large)
end
HTML version of Scripted Foils prepared 8 November 1995

Foil 26 Formalism for Convergence of Stationary Iterative Methods

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Scripted Foils prepared 8 November 1995

Foil 27 Eigenvalue Analysis of Iterative Methods

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Method converges if and only if all |li| < 1
We can calculate l i in simple cases. What counts is largest value of |l i| as this term will dominate in limit of large k where k counts iterations.
HTML version of Scripted Foils prepared 8 November 1995

Foil 28 Estimation of largest Eigenvalue in One Dimension

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Scripted Foils prepared 8 November 1995

Foil 29 Eigenvalues and Convergence Rate of Jacobi Iteration

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
The Jacobi Iteration Matrix G=M-1N is given by
HTML version of Scripted Foils prepared 8 November 1995

Foil 30 Difficult and Easy Eigenfunctions Controlling
Convergence of Jacobi Iteration

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
What does "difficult" eigenfunction mean?
Pictures illustrate that "diffucult" eigenfunction sinpx is "long" wave length - "local" iteration algorithm converges slowly whereas local iteration converges very fast for short wavelength
HTML version of Scripted Foils prepared 8 November 1995

Foil 31 Decoupling of Even and Odd Grid Point Updates in Basic Jacobi Iteration

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
There is a minor confusion as shortest wavelength eigensolutions with n = (N-1) has a large eigenvalue whose modulus |lN-1| = l1 (lN-1 = -l1) is equal to that of "difficult" long wavelength case
One would expect it to be damped strongly. This is an artifact of this iteration scheme as even (l = 0, 2, 4 ....) and odd grid points are decoupled
Update of even l points only involves odd l
Update of odd l points only involves even l
We will return to this when we discuss relaxation
HTML version of Scripted Foils prepared 8 November 1995

Foil 32 Damping of Eigenfunctions of Short and Long Wavelength

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Smallest (in modulus) eigenvalue corresponds to most rapidly varying eigenfunction - these are x dependences to which local iteration most sensitive
HTML version of Scripted Foils prepared 8 November 1995

Foil 33 Extension of Jacobi Eigenvalue Analysis to two or more Dimensions

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Scripted Foils prepared 8 November 1995

Foil 34 Direct Solution Method for Ax=b

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Consider Ax = b solved "directly" which is Gaussian elimination where one succesively removes
  • x1 from Equation 2 to N,
  • x2 from Equations 3 to N etc.
Then this has memory requirement of order N2 and computational complexity of order N3
This is modified somewhat when you consider matrices A with a lot of zeroes and try hard to exploit these zeros i.e. avoid doing calculations which are irrelevant as adding or multiplying by zero
Of course this cannot be done by testing on matrix element being zero as modern computers do floating point arithmetic faster than or at least as fast as test!
Rather one arranges loops to not include zero elements -- if possible!
HTML version of Scripted Foils prepared 8 November 1995

Foil 35 Banded Matrix Computational Complexity

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
One can show that in a general sparse matrix, it is straightforward to preserver the "end" zeros
000...000X000...000XXX000...000X000...000 shows structure of a row of A in 2D Laplace example
The first and last zeros can be explicitly taken into account by setting range of for loops properly
The inside zeros "fill" i.e. become nonzero during process of Gaussian elimination
Thus if bandwidth B i.e.
000...000X000...000XXX000...000X000...000
Then computational complexity is not N3 as for a full (no zeros accounted) but NB2
HTML version of Scripted Foils prepared 8 November 1995

Foil 36 Comparison of Computational Complexity between Direct and Iterative Methods

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Note G here is size of number of grid points in each dimension
One dimension Nx = G Direct time a G (as tridiagonal matrix) Sparse time a G.G2 = G3
Two dimensions Nx = Ny = G Direct time a G2.G2 = G4 (G2xG2 banded matrix - band size G) Sparse time a G2 (one iteration) .G2 (# iterations) = G4
Three dimensions Nx = Ny = Nz = G Direct time a G3.(G2)2 = G7 (G3xG3 banded matrix - band size G2) Sparse time a G3 (one iteration) .G2 (# iterations) =G5
SOR and conjugate gradient will make iterative methods "look better" as number of iterations proportional to G and not G2
HTML version of Scripted Foils prepared 8 November 1995

Foil 37 Memory Use in Direct and Iterative Methods

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
One Dimension: Both Sparse and Direct Methods use memory of order G -- the matrix size
In two dimensions,
  • Direct Method: Space is of order G3
  • Sparse Method: Space is of order G2
In three dimensions,
  • Direct Method: Space is of order G5
  • Sparse Method: Space is of order G3
HTML version of Scripted Foils prepared 8 November 1995

Foil 38 Over Relaxation (SOR) and Relation to Jacobi and Gauss-Seidel

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Jacobi and Gauss Seidel give a formula for x(k+1) in terms of x(k) call this x(k+1)
Overrelaxation forms x(k+1) = w x(k+1) + (1-w)x(k)
Typically only 0 < w < 2 is sensible w < 1 is relaxation 1 < w < 2 is over relaxation
First consider relaxation for Jacobi x(k+1) = wx(k+1) + (1-w)x(k)
There is an iteration matrix
  • G=M-1 N which on diagonalization we called K
  • with G=PTKP and P an orthogonal matrix
HTML version of Scripted Foils prepared 8 November 1995

Foil 39 Over Relaxation Eigenvalues and Matrices for Jacobi Iteration

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
The iteration matrices are related by
GJOR(w) = wGJ + (1-w )I
where I is the identity matrix and subscript JOR stands for Jacobi Over Relaxation
This relation is still true after diagonalization and is preserved for eigenvalues
lJOR(w) = wlJ + (1-w)
We need to look at those values of lJOR which are largest and smallest
These are:
lJOR|max = 1- p2/2N2 = 1- e
lJOR|min = -1+ p2/2N2 = -1+ e
HTML version of Scripted Foils prepared 8 November 1995

Foil 40 Jacobi Iteration Eigenvalues as a function of Over Relaxation Parameter

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
lJOR|max(w) = 1 - ew
  • This is decreased in absolute value for w > 1, increased for w < 1
lJOR|min(w) = 1+ we - 2w
  • This is just the opposite
  • Increased for w > 1, decreased for w < 1
The best value of w is w = 1 i.e. Best is Original Jacobi iteration as one must minimize the maximum over all values of eigenvalue moduli |l| and for Jacobi one canNOT use overrelaxation
HTML version of Scripted Foils prepared 8 November 1995

Foil 41 Jacobi Relaxation for Over Relaxation Parameter w =1/2

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
For w=1/2, one has
x(k+1) =1/2[x(k) + x(k+1 ) ] where J denotes Pure Jacobi
and subscript JOR stands for Jacobi Over Relaxation again
This has "update" matrix in two dimensions
xpoint = 1/2 xpoint + 1/8 times x of four neighbors
We now "couple" even and odd grid points which were decoupled in original Jacobi
Corresponding eigenvalue of most rapidly varying eigenfunction is
now lJOR|min ~ 0
not lJOR|min ~ -1 as before
HTML version of Scripted Foils prepared 8 November 1995

Foil 42 Introduction to Gauss-Seidel Iterative Approach

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Jacobi has a set x(k-1) and then replaces it bodily by x(k)
After we find x(k), we know all of x(k-1) and x1(k).
In Gauss Seidel use x1(k), x2(k-1) .... xn(k-1) to find x2(k).
In Jacobi, one uses x1(k-1), x2(k-1) .... xn(k-1) to find x2(k)
Gauss Seidel - general prescription - always use latest values of xj
There are many possible, Gauss Seidel's - one for each ordering of variables
HTML version of Scripted Foils prepared 8 November 1995

Foil 43 6:Mathematical and Pseudo Code Form of Gauss Seidel Iteration Method

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 44 7:Mathematical (Matrix) Form of Gauss Seidel

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 45 8:Parallelism in Gauss-Seidel Iteration

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 46 9:Matrix Example Stencil

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 47 10:Matrix---Wavefront Parallelism for Gauss Seidel

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 48 11:The Red-Black Two Phase Parallel Gauss Seidel Iteration

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 49 12:Analysis of Parallel Red Black Gauss Seidel

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 50 13:Eigenvalues of Gauss Seidel Iteration Matrix

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 51 14:Comparison of Convergence of Gauss-Seidel and Jacobi Iteration

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 52 15:Successive Overrelaxation Iteration Method (SOR)

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 53 16:Convergence of SOR Compared to Jacobi and Gauss Seidel

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 54 17:Estimate of Over Relaxation Parameter

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
HTML version of Scripted Foils prepared 8 November 1995

Foil 55 18:Pseudo Code for SOR---Successive Over Relaxation

From CPS615 Module on Iterative PDE Solvers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
See Original Foil
© on Tue Oct 28 1997