Multi Grid Presentation

Jos van Kan

j.vankan@math.tudelft.nl

TU Delft

Two Grid Algorithm

1: Presets: u_{h}^{0}, r_{h}^{0} = f_{h} − Au_{h}^{0} 2: u_{h}^{prs} = S(u_{h}^{0}, b, A, n_{0}){Presmoothing}

3: r_{H} = R_{Hh}r_{h}

4: Solve A_{H}c_{H} = r_{H} 5: u_{h}^{cgc} = u_{h}^{p} + P_{hH}c_{H} {Coarse Grid Correction} 6: u_{h}^{pos} = S(u_{h}^{cgc} , b, A, n_{1}){Postsmoothing} 1: Presets: u_{h}^{0}, r_{h}^{0} = f_{h} − Au_{h}^{0} 2: u_{h}^{prs} = S(u_{h}^{0}, b, A, n_{0}){Presmoothing}

3: r_{H} = R_{Hh}r_{h}

4: Solve A_{H}c_{H} = r_{H} 5: u_{h}^{cgc} = u_{h}^{p} + P_{hH}c_{H} {Coarse Grid Correction} 6: u_{h}^{pos} = S(u_{h}^{cgc} , b, A, n_{1}){Postsmoothing} 1: Presets: u_{h}^{0}, r_{h}^{0} = f_{h} − Au_{h}^{0} 2: u_{h}^{prs} = S(u_{h}^{0}, b, A, n_{0}){Presmoothing}

3: r_{H} = R_{Hh}r_{h}

Multi Grid Algorithm

4: Solve A_{H}c_{H} = r_{H} 5: u_{h}^{cgc} = u_{h}^{p} + P_{hH}c_{H} {Coarse Grid Correction} 6: u_{h}^{pos} = S(u_{h}^{cgc} , b, A, n_{1}){Postsmoothing} MGRecursive (A_{ℓ}, r_{ℓ}, c_{ℓ}, ℓ) if ℓ < p − 1 then

c_{ℓ} = S(0, r_{ℓ}, A_{ℓ}, n_{0}){Presmoothing} r_{ℓ+1} = R_{ℓ}(r_{ℓ} − A_{ℓ}c_{ℓ}) {Calculate coarse grid residual} A_{ℓ+1} = R_{ℓ}A_{ℓ}P_{ℓ+1} {Calculate coarse grid matrix} call MGRecursive (A_{ℓ+1}, r_{ℓ+1}, c_{ℓ+1}, ℓ + 1) c_{ℓ} = c_{ℓ} + P_{ℓ+1}c_{ℓ+1} {Coarse grid correction} c_{ℓ} = S(c_{ℓ}, r_{ℓ}, A_{ℓ}, n_{1}) {Postsmoothing}

else Solve A_{p−1}c_{p−1} = r_{p−1}{Direct solution on coarsest level}

end if

Multi Grid Presentation – p. 3/3

MGRecursive (A_{ℓ}, r_{ℓ}, c_{ℓ}, ℓ) if ℓ < p − 1 then

c_{ℓ} = S(0, r_{ℓ}, A_{ℓ}, n_{0}){Presmoothing} r_{ℓ+1} = R_{ℓ}(r_{ℓ} − A_{ℓ}c_{ℓ}) {Calculate coarse grid residual} A_{ℓ+1} = R_{ℓ}A_{ℓ}P_{ℓ+1} {Calculate coarse grid matrix} call MGRecursive (A_{ℓ+1}, r_{ℓ+1}, c_{ℓ+1}, ℓ + 1) c_{ℓ} = c_{ℓ} + P_{ℓ+1}c_{ℓ+1} {Coarse grid correction} c_{ℓ} = S(c_{ℓ}, r_{ℓ}, A_{ℓ}, n_{1}) {Postsmoothing}

else Solve A_{p−1}c_{p−1} = r_{p−1}{Direct solution on coarsest level}

end if

Multi Grid Presentation – p. 3/3

MGRecursive (A_{ℓ}, r_{ℓ}, c_{ℓ}, ℓ) if ℓ < p − 1 then

c_{ℓ} = S(0, r_{ℓ}, A_{ℓ}, n_{0}){Presmoothing} r_{ℓ+1} = R_{ℓ}(r_{ℓ} − A_{ℓ}c_{ℓ}) {Calculate coarse grid residual} A_{ℓ+1} = R_{ℓ}A_{ℓ}P_{ℓ+1} {Calculate coarse grid matrix} call MGRecursive (A_{ℓ+1}, r_{ℓ+1}, c_{ℓ+1}, ℓ + 1) c_{ℓ} = c_{ℓ} + P_{ℓ+1}c_{ℓ+1} {Coarse grid correction} c_{ℓ} = S(c_{ℓ}, r_{ℓ}, A_{ℓ}, n_{1}) {Postsmoothing}

else Solve A_{p−1}c_{p−1} = r_{p−1}{Direct solution on coarsest level}

end if

Multi Grid Presentation – p. 3/3

MGRecursive (A_{ℓ}, r_{ℓ}, c_{ℓ}, ℓ) if ℓ < p − 1 then

c_{ℓ} = S(0, r_{ℓ}, A_{ℓ}, n_{0}){Presmoothing} r_{ℓ+1} = R_{ℓ}(r_{ℓ} − A_{ℓ}c_{ℓ}) {Calculate coarse grid residual} A_{ℓ+1} = R_{ℓ}A_{ℓ}P_{ℓ+1} {Calculate coarse grid matrix} call MGRecursive (A_{ℓ+1}, r_{ℓ+1}, c_{ℓ+1}, ℓ + 1) c_{ℓ} = c_{ℓ} + P_{ℓ+1}c_{ℓ+1} {Coarse grid correction} c_{ℓ} = S(c_{ℓ}, r_{ℓ}, A_{ℓ}, n_{1}) {Postsmoothing}

else Solve A_{p−1}c_{p−1} = r_{p−1}{Direct solution on coarsest level}

end if

Multi Grid Presentation – p. 3/3