A Multigrid Tutorial

Vhenson

Description

Multigrid for nonlinear problems: an overviewVan Emden HensonCenter for Applied Scientific ComputingLawrence Livermore National [e-mail]://www.casc.gov/CASC/people/hensonJanuary 23, 2003This work was performed, in part, under the auspices of the United States Department of Energy by University of California Lawrence Livermore National Laboratory under contract number W-7405-Eng-48.Outline• Multigrid: a 30-second introduction• The scalar Newton’s method• Newton’s method for systems• Multigrid for Newton’s method: Newton-MG• Nonlinear multigrid: full approximation storage (FAS)• Numerical examples of Newton-MG and FAS2o f 3 8The 1-d Model Problem− ∆u = f• Poisson’s equation: in [0,1], with boundary conditions .u ( 0 ) = u ( 1 ) = 0• Discretized as:2u = u = 0−u +2u −u =h f0 Ni −1 i i +1 iAu = f• Leads to the Matrix equation , where f u 12 − 1  1     fu− 1 2 − 1 22   u  f   − 1 2 − 133A = , u = , f =         u  N − 2− 1 2 − 1 f N − 2  u  N − 1− 1 2  fN − 1 3o f 3 8Weighted Jacobi Relaxation• Consider the iteration:ω2( n ew ) ( o ld ) ( o ld ) ( o ld )u ← ( 1 − ω ) u + ( u + u + h f )i i i − 1 i + 1 i2• Letting A = D-L-U, the matrix form is:− 1 2 − 1( new ) ( old )u = ( 1 − ω ) I + ωD ( L + U ) u + ωh D f2 − 1( old ).= R u + ωh D fω( ...

Informations

• Publié par: Lomif
• Nombre de lectures: 13
• Langue: English

Extrait

Multigrid for nonlinear problems: an overview

Van Emden Henson CenterforAppliedScientificComputing LawrenceLivermoreNationalLaboratory

vhenson@lgovnl.

http://www.casc.gov/CASC/people/henson

January23,2003

This work was performed, in part, under the auspices of the United States Department of Energy by University of California Lawrence Livermore National Laboratory under contract number W-7405-Eng-48.













Outline

Multigrid: a 30-second introduction

The scalar Newtons method

Newtons method for systems

Multigrid for Newtons method: Newton-MG

Nonlinear multigrid: full approximation storage (FAS)

Numerical examples of Newton-MG and FAS

2 of 38

 



The 1-d Model Problem

Poissons equation: −  ∆  u  =  [0,1], with boundary in conditions u  (  0  )  =  u  (  1  )  =  0  . Discretized as: 2 −u i−1 +2u i −u i+1 =h f

u=u

0N

=0

Leads to the Matrix equation u  =  , where

 −1 =       −1 2 − 2 1 −1 2−1    ,     u       =    u N u u u 1 3 2 −2         ,  f       =   f N f f 2 1 3 −2           −1 −1 2− 2 1   u N−1 f N1 −

3 of 38

Weighted Jacobi Relaxation

 Consider the iteration: u i ( wn e) ← (1−ω)u old i ) + ω 2 (u i o − l 1 d) +u o i+ l 1 d) +h 2 f i )

 Letting-L-U=DA,the matrix form is:

u (new) = (1ω−)I+ ωD −1 (L+U)u old) + ωh 2 D −1 f

=R ω u (old) + ωh 2 D −1 f .

e≡u (exact) −u (approx)  It is easy to see that if , then

e (new) =R ω e (old)

4 of 38

Relaxation Smoothes the Error

 Initial error, 2 1 0 - 1 - 2 0 0 . 5 1  Error after 35 iteration sweeps:

2 1 0 - 1 - 2

0

0 . 5

1

Manyrelaxation schemes havethemootsgnih propertyw,rehe oscilrytoa modesoftheerror are eliminated effectively,but smoothmodesare damped veryslowly.

5 of 38

Smooth error can be represented accurately on a coarse grid

 A smooth function: 1 0 . 5 0 - 0 . 5 - 1 0 0 . 5 1  Can be represented by linear interpolation from a coarser grid: 1 0 . 5

0 - 0 . 5 - 1 0

0 . 5

1

On the coarse grid, the smooth error appears to be relatively higher in frequency: in the example it is the 4-mode, out of a possible 16, on the fine grid, 1/4 the way up the spectrum. On the coarse grid, it is the 4-mode out of a possible 8, hence it is 1/2 the way up the spectrum.

Relaxation will be more effective on this mode if done on the coarser grid!!

6 of 38









Coarse-grid Correction

Perform relaxation on u  h  =  f  on fine grid until error is smooth.

Compute residual, r  2 h  =  f  −  A  u  h  and transfer to the coarse grid r  2  h  =  I  h  r  h .

Solve the coarse-grid residual equation to obtain the error: 2h e 2h =r 2h , ∴e 2h = (A 2h ) 1 r 2h

Interpolate the error to the fine grid and correct the fine-grid solution: u h ←u h +I 2h e 2h

7 of 38

Coarse-grid Correction

Relax on u h =f Compute r h =f−A u h

Restrict r 2h =I h 2 r h

Correct u←u+e

Solve 2 e 2h =r 2h − e 2h = (A 2h ) 1 r 2h

Interpolate e h ≈I 2h e 2h

8of38

Tools Needed

 Interpolation and restriction operators:

...

0.5   1.0    0 50 5 0 25 1 0 0 25 0 1 0 2 h h     =  .  0 1 . .0 1 505 50 0         ,  I h 2h    = 0 010 10   ,  I h 2h    = 0.25 1.00 0 . . 52 215.0 0.25     . . . . Linear Injection Full-weighting Interpolation  Coarse-grid Operator A  2  . Two methods: (1) Discretize equation at larger spacing (2) Use Galerkin Formula: A 2 =I h 2 A I 2h

9 of 38

Recursion: the ( ν ,0) V-cycle

 Major question: How do we solve the coarse-grid residual equation?swAnre:erucsroin! u h ←G ν (A,f) u←u+e 2 ←I h 2 (f−A u h ) e h ←I 2h u 2h u 2h ←G(A 2 ,f 2 ) u 2 u 2 e 2 4 ←I 2 4 h (f 2 −A 2 u 2h ) e 2h ←I 2 4h u 4h u 4h ←G ν (A 4 ,f 4 ) u 4 ←u 4 +e 4 8 ←I 8 4h (f 4 −A 4 u 4h ) e 4h ←I 8 4 h u 8h u 8h ←G ν (A 8 ,f 8 ) u 8 ←u 8 +e 8

e H = (A) −1 f

10 of 38

lt Mu o i u g t r  i s d m u o s o e t s h   c e o r a r r o s r e   c g o r m id p s o  n t e o n  t d s amp

smoother

Finest Grid

A Multigrid V-cycle

Prolongation- transfer from coarse to fine grid

Restriction- transfer from fine to coarse grid

First Coarse Grid

Note: smaller grid

11of38