Kurs numalg10 [NADA, KTH]

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

7.5 Credits

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

Most recent changes on 21 December 2010

Exam

The written exam will take place in room D31, Thursday December 16, 2010, from 14-19. Should the room D31 become full, please go to lecture hall D2 where there will be extra places available.

Re-Exam

A re-exam will take place in room 1535, floor 5, CSC, Wednesday March 16 from 13.00-17.00. Please contact Mattias Sandberg by mail in advance if you plan to attend.

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, 2010. Examination is by homework and computer assignments and one written exam.

Teacher

Mattias Sandberg, room 1526, CSC, Lindstedtsvägen 3, floor 5. Telephone: 08-790 6333. E-mail: msandb(at)kth.se

Office Hours

Fridays 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, 2010, Monday 25 October. Preliminary times and dates are

Monday 25 Oct at 13-15 in room E51.
Wednesday 27 Oct at 13-15 in room H21.
Monday 1 Nov at 8-10 in room E51.
Wednesday 3 Nov at 13-15 in room L44.
Wednesday 10 Nov at 13-15 in room E31.
Thursday 11 Nov at 13-15 in room 4523.
Monday 15 Nov at 8-10 in room 4523.
Wednesday 17 Nov at 13-15 in room Q24.
Monday 22 Nov at 8-10 in room 4523.
Wednesday 24 Nov at 13-15 in room 4523.
Monday 29 Nov at 8-10 in room 4523.
Monday 6 Dec at 13-15 in room 4523.

Room 4523 is a seminar room at the Numerical Analysis department, Lindstedtsvägen 3, floor 5. The entrance door to the department on floor 5 is locked. Knock the door, or ring the doorbell!

Homework

Homework number one, due Thursday, November 11, 2010.,

Homework number two, due Wednesday, November 24, 2010. If a correct solution to the homework is handed in before that date, two bonus points will be awarded to the final written exam.

Homework number three, due Wednesday, December 1, 2010. If a correct solution to the homework is handed in before that date, two bonus points will be awarded to the final written exam. This file, by Michael Hanke, contains information on how to construct the discrete Laplacian in Matlab. Note, however, that the expression given for the discrete Laplacian lacks the factor 1/(h*h).

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. This book is electronically available to all KTH students via the KTH Library, but unfortunately not in a very readable format.
"Lecture Notes: Advanced Numerical Methods" by Michael Hanke. Available at the CSC Studentexpedition by the time the course starts.
"A short course on fast multipole methods", by Rick Beatson and Leslie Greengard. Available on Greengards homepage here.,
"A fast algorithm for particle simulations", by Greengard and Rokhlin. Journal of Computational Physics 73, 325-348 (1987).

Study Questions

Here is a list of questions to prepare for the exam. The questions in the written exam will be taken from this list. The list is now in its final form.

Reading Instructions

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 and 88-119 are covered. The texts by Greengard and Rokhlin are extra material for the interested student. The questions on the written exam will be taken from the list of study questions.

Course requirements

Written examination (3 credits); Computer assignments (4.5 credits)

Course Evaluation

Here is the course evaluation for the 2010 course.

Up to Nada's home page.

Responsible for this page: <infomaster@nada.kth.se>
Latest change November 5, 2010
Technical support: <webmaster@nada.kth.se>