Seminar Multigrid Methods - Winter 12

Term

Winter 12

Lecturer

Prof. Dr. Michael Bader, Prof. Dr. Thomas Huckle, Benjamin Peherstorfer, Marion Weinzierl

Time and Place

t.b.a.

Audience

Students from Master Computational Science and Engineering (IN2183), Informatics (IN2107) and Mathematics, and Bachelor Informatics (IN0014) and Mathematics

Tutorials

-

Exam

-

Semesterwochenstunden / ECTS Credits

2 SWS (2S) / 4 Credits

TUMonline

Seminar page

---

Description

Multigrid Methods are (almost incredibly) fast solvers for certain problems in Scientific Computing - mainly systems of equations arising from the discretisation of PDE-based models. For simple model problems, such as the Poisson equation, multigrid solvers can be tuned to solve systems of millions to billions of equations with constant amount of work (some 20 flops in ideal cases) per unknown. However, for realistic scenarios and more complicated model equations, multigrid methods have to be modified to retain their optimal complexity. In addition the efficient implementation of multigrid methods, in particular on massively parallel hardware, is still an area of active research.

The student presentation planned for this seminar will thus explore and introduce to multigrid basics as well as recent research on the numerics and algorithmics of multigrid approaches (see the list of topics below).

Prerequisites

The following paper gives a good introduction into the basic idea of multigrid:

• "Why multigrid methods are so efficient" (I. Yavneh, 2006)

We would expect all participants to be familiar with the numerical terms and concepts used in this paper before the seminar starts.

Announcements

• The seminar will be completely in English, so the students also have to give their talks and to write their papers in English.

• Preliminary meeting: July 11, 10.30 - 12.00 in room MI 02.09.023.
  • The slides of the meeting are available here

• Kick-off with final assignment of topics: Monday, October 22, 9.00-11.30 in room MI 02.07.023 (topics can, however, already be chosen before the semester break)

• Presentations will take place on Mondays, 9.15 - 11.30, in room MI 02.07.023. Presentation sessions will start on December 3 (for exact dates see Kick-off slides).

• Due to some shifts in the talks we will also have a presentation session on January 21!

Slides

• Kick-Off slides

Topics

• Multigrid Basics:
  • Hierarchical Transformation Multigrid
  • Semidefinite Systeme (assigned)
  • Adaptive multigrid, MLAT, FAC (assigned)
  • Multigrid for non-linear problems (assigned)

• Algebraic Multigrid:
  • Classical AMG (assigned)
  • (Alpha-)Smoothed Aggregation (assigned)
  • Parallel AMG (assigned)

• Operator-dependend Multigrid:
  • Introduction to operator-dependend multigrid
  • (Alpha-)BoxMG

• Convection-diffusion equation
  • Introduction to solving the convection-diffusion equation with multigrid methods (assigned)
  • Convection-dominated problems, closed characteristics (+)

• Further topics:
  • Multigrid for regularization in image restauration (assigned)
  • Full Multigrid as a Regularization Method (assigned)
  • Analysis of multigrid methods, Local Fourier Analysis
  • Smoother: SPAI, ... (+)

(+) will only be assigned when all other topics are covered

Literature

• Trottenberg, Oosterlee, Schüller: "Multigrid"

• Briggs, Henson, McCormick: "A Multigrid Tutorial", 2nd edition

• Publications in Journals etc.

Requirements

For successful completion of the seminar course you have to fulfil the following tasks:

• solid understanding of your topic
• implementation of the underlying algorithm or similar
• writing of a paper (about 8 pages)
• presentation (30 min topical presentation + 10 min presentation of implementation results + discussion)
• participation in the presentations of all other participants
• deadlines: see kick-off slides

The paper template is available here. Usage of Latex is required.