Kurs numalg12 [NA, KTH]

DN2230 Fast Numerical Algorithms for Large-Scale Problems, autumn 2012

7.5 Credits

Formal description, that is, the text in the study-handbook.

Most recent changes on 8 May 2013.

News

News about the re-exam: See below

The December 2012 exam has been corrected, and may be collected at KTH Mathematics student expedition.

Schedule change. Look at KTH Time Edit, or below, for the valid schedule.

Re-Exam

A re-exam will be held Friday June 7, 2013, from 09.00-13.00, in seminar room 319, Teknikringen 14, floor 3. Ring the bell or knock the door to enter the corridor. Please inform me in advance if you intend to take the re-exam.

Exam

The written exam will take place Monday December 10, 2012, from 09-13. In order to be allowed to write the exam the student must sign up for it no later than two weeks before the exam on "My Pages". This exam reservation is active from four weeks before the exam until two weeks before the exam. In order to be able to sign up for the exam the student must also sign in as "active" in the course, which is done in the KTH Rapp system.

Teaching and Examination

There will be twelve two-hour lectures from October through December, where the theory of the methods will be presented and discussed. The first lecture will be in week 43, 2012. Examination is by homework and computer assignments and one written exam.

Teacher

Mattias Sandberg, room 311, Teknikringen 14, floor 3. Telephone: 08-790 6633. E-mail: msandb(at)kth.se

Office Hours

Tuesdays 15-16. If you want to meet me at another time it is safest to make an appointment in advance via e-mail.

General Description and Aim

The course is devoted to the introduction of advanced numerical methods in Scientific Computing for large scale applications. The aim of the course is to give the students an introduction to the construction principles of advanced numerical methods so that they will be able to understand, use, and develop efficient algorithms for large scale problems.

Topics

Fast Multi-pole Methods. The Multi-pole method was invented to speed up computations for the n-body problem. This is the problem of computing the evolution of a system of particles that interact via Coulomb forces, e.g. stars or electrically charged atoms. The essential aim is to show that using cleverly chosen approximations and divide- and conquer- techniques an intentionally $O(n^2)$ computational process can be reduced to $O(\log\frac{1}{\eps}n\log n)$ complexity if $\eps$ denotes a given (desired) precision, and $n$ is the number of particles. The method can also be used to solve some partial differential equations by reformulation as integral equations.
Eigenvalue algorithms. The QR Algorithm, related with the Gram-Schmidt orthogonalization procedure, will be presented. We will also see why it is essential to reduce the matrix, whose eigenvalues we seek, to Hessenberg or tridiagonal form, and how this can be done.
Krylov-type Iteration Methods. A well-established technique for the solution of large sparse linear systems of equations with a symmetric and positive definite coefficient matrix is the (preconditioned) conjugate gradient method. Here we will show how it can be extended to more general problems.
Multilevel Methods. These methods are well-known as efficient tools for the iterative solution of linear (and nonlinear) systems of equations arising while discretizing partial differential equations. We will focus primarily on the Multigrid method.

The first lecture is in week 43, 2012, Tuesday 23 October. Preliminary times and dates are

Tuesday 23 Oct at 8-10 in room E34.
Friday 26 Oct at 13-15 in room M38.
Tuesday 30 Oct at 8-10 in room E34.
Friday 2 Nov at 13-15 in room M38.
Tuesday 6 Nov at 8-10 in room E34.
Friday 9 Nov at 13-15 in room M38.
Tuesday 13 Nov at 8-10 in room E34.
Friday 16 Nov at 13-15 in room M38.
Tuesday 20 Nov at 8-10 in room E34.
Friday 23 Nov at 13-15 in room M38.
Tuesday 27 Dec at 8-10 in room M38.
Friday 30 Nov at 13-15 in room M38.

Course Plan

The list below is the plan for what is to be discussed at the lectures. The plan might be adjusted slightly if some part of the course takes more or less time than expected.

Introduction, course overview. Introduction to Multi Grid
Multi Grid
Complexity of Multi Grid
Non-linear Multi Grid. Beginning eigenvalue problems. Power Method
Inverse Iteration, Simultaneous Iteration, QR-factorization
Simultaneous Iteration, QR algorithm, Rayleigh Quotient
QR algorithm continued
Iterative methods: Krylov spaces, Arnoldi iteration, GMRES
Convergence of GMRES, Lanczos Iteration
Conjugate Gradient Method
Other iterative methods: BiConjugate Gradient, Quasi-Minimal Residual, CGS. Preconditioning. The Multipole Method.
Multipole Method

Homework

Homework number one, due Friday, November 2, 2012.

Homework number two, due Friday, November 16, 2012.

Homework number three, due Tuesday, November 27, 2012.

Literature

I will cover parts of the following texts:

The book "Numerical Linear Algebra", by Lloyd N. Trefethen and David Bau. ISBN: 0-89871-361-7.
The book "Multigrid", by Ulrich Trottenberg, Cornelis Oosterlee, and Anton Schuller. ISBN: 0-12-701070-X.
"Lecture Notes: Advanced Numerical Methods" by Michael Hanke. Available at the KTH Mathematics Studentexpedition by the time the course starts.

Study Questions

Here is a list of questions to prepare for the exam. All but one question on the exam will be taken from this list. The list is now complete, i.e.\ no more questions will be added before the exam.

Reading Instructions

In "Multigrid", by Trottenberg et al. sections 1, 2.1-2.6, 2.8.2, 3.1-3.3, 5.3.1-5.3.5 are covered. In "Numerical Linear Algebra", by Trefethen and Bau, chapters 7, 8, 10, 24-29, 32, 33, 35, 36, 38-40 are covered. In the lecture notes on advanced numerical methods by Michael Hanke, the pages 9-67 are covered. You may also want to read section 3.3 and 3.4 in Hanke's text on the multigrid method.

Course requirements

Written examination (3.5 credits); Computer assignments (4 credits)

Up to Nada's home page.

Responsible for this page: <infomaster@nada.kth.se>
Latest change May 8, 2013
Technical support: <webmaster@nada.kth.se>