Scribd
Upload
559 views

MultiGrid Method (CFD) by Atta

A powerpoint presentation on Multigrid method used in CFD (Computational Fluid Dynamics) Software's. (By: Engr. Atta ur Rehman Shah)

Uploaded by

Atta ur Rehman
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
559 views

MultiGrid Method (CFD) by Atta

A powerpoint presentation on Multigrid method used in CFD (Computational Fluid Dynamics) Software's. (By: Engr. Atta ur Rehman Shah)

Uploaded by

Atta ur Rehman
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 18

MULTI-GRID METHOD

Computational Fluid Dynamics (CFD) – ME-524

Engr. Atta ur Rehman Shah)


Email: [email protected]
Cell # 0092 321 5775477

GIK Institute of Engineering Sciences & Technology Pakistan


Outlines
 Introduction
 Definitions
 Classification
 Common Multigrid Schedule
 Multigrid Cycles
 Cost Comparison
 Multigrid Guidelines
 Multigrid Applications
 Related Methods
 References
Introduction
 Multigrid methods are based on the idea of defining
coarser grids on which a low frequency error will be
seen as a high frequency one.

 Multigrid methods effectively reduce the distribution of


low frequency errors which makes them the ideal
ingredient to be used with standard solvers.

 Note: Multigrid is not a solver. It is a technique used in


conjunction with a linear solver to yield a better
convergence rate.
Fine Grids Vs Coarse Grids
Definitions
 Agglomeration: The process of defining the coarser grids involves what is
called Agglomeration, i.e. the combination of several nodes or control
volumes or coefficients from the original grid.

 Restriction: The interpolation method used to inject the error from a fine
grid to a coarser one.

 Prolongation or Interpolation: The inverse of restriction and is defined as


the interpolation method used to inject the residual from the coarse grid to
the finer one.
Classification
Multigrid methods are classified into two branches

 Full Geometric Multigrid


 Algebraic Multigrid or AMG
Full Geometric Multigrid
In the Geometric Multigrid, agglomeration of the
nodes (cells, elements, or control volumes) takes
place on the geometric level, and a set of new data
structures representing the coarse grids need to be
constructed for each level. This method is usually
difficult to deal with when using the finite volume
method since the FVM is based on a cell centered
discretization which makes it difficult to define
irregularly shaped control volumes.
Algebraic Multigrid or AMG

The Algebraic Multigrid performs the


agglomeration using the coefficient matrix only
(hence the name algebraic). In the AMG method,
specially chosen coefficients of the matrix are
combined together to form a new coefficient matrix
representing the coarser grid and no new
discretization is required on the coarse grids.
A Common Multigrid Schedule
 Full Multigrid V Cycle:
final solution

finest grid k×k

k/2×k/2

...

coarsest grid 1×1


time

=relax =Prolongation =restriction


Relax

Restrict Interpolate

Relax

Relax

Relax

Relax
Multigrid Cycles

Finest Grid

Coarsest Grid
Multigrid Sketch in 1D
 Consider a 2m+1 grid in 1D for simplicity

 Let P(i) be the problem of solving the discrete Poisson equation on a 2i+1
grid in 1D
 Write linear system as T(i) * x(i) = b(i)

 P(m) , P(m-1) , … , P(1) is sequence of problems from finest to coarsest


Multigrid Sketch in 2D
 Consider a 2m+1 by 2m+1 grid in 2D
 Let P(i) be the problem of solving the discrete Poisson equation on a 2i+1 by
2i+1 grid in 2D
 Write linear system as T(i) * x(i) = b(i)

 P(m) , P(m-1) , … , P(1) is sequence of problems from finest to coarsest


Cost Comparison
on 2-D Poisson Equation, k×k grid, n=k2 unknowns

METHOD COST
Gaussian Elimination O(n3)
Gauss-Seidel O(n2logn)
Conjugate Gradient O(n1.5)
FFT/cyclic reduction O(nlogn)
multigrid O(n)
optimal!
Multigrid Guidelines
 “multigridders” prefer structured grids
 grid and relaxation method are the only parts of the method that
are highly problem-dependent; restriction and interpolation are
generic
 on complex domains, need extra relaxation steps near boundary
 for rough boundary conditions
 for concave corners
 grid can be adaptive: can restrict processing at finer levels to
subdomains
 schedule parameters (how many relaxation steps and V cycles) can
be:
 fixed
 accommodative
Multigrid Applications
 computational fluid dynamics (CFD)
 structured grid generation
 ill-posed (underdetermined) problems
 global optimization
 solid mechanics
 quantum chemistry
Related Methods
 unstructured multigrid
 uses an unstructured grid (irregular topology), not structured one
 this complicates relaxation, restriction, & interpolation, but permits
solution on complex domains (e.g. around an aircraft wing with
flaps)
 algebraic multigrid
 multigrid without the grid
 analyze and do clustering on graph implied by matrix A
 input is A only -- no high level problem knowledge
 domain decomposition
 divide domain into (possibly overlapping) pieces
 solve alternately on each piece, using solution of other pieces as
boundary conditions
References
 Paul Heckbert ,Introduction to Scientific Computing (Computer
Science Department Carnegie Mellon Univers)

 Dragica Vasileska , Multi-Grid Method

 http://www.cfd-online.com

You might also like