DN2230 Fast Numerical Algorithms for Large-Scale Problems, autumn 2011
7.5 Credits
Formal description,
that is, the text in the study-handbook.
Most recent changes on 20 January 2012.
News
The deadline for bonus points on homework 1 is moved to Friday November 11.
Course Evaluation
Exam
The written exam will take place in room V21, Wednesday December 21,
2011, from 14-18.
Re-Exam
The re-exam takes place Thursday February 2 from 14-18 in seminar room 4523, Lindstedtsvägen 3, floor 5.
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, 2011.
Examination is by homework and computer assignments
and one written exam.
Fridays 15-16 (except November 4). 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, 2011, Monday 24 October.
Preliminary times and dates are
Monday 24 Oct at 8-10 in room K53.
Wednesday 26 Oct at 8-10 in room D33.
Monday 31 Nov at 8-10 in room L31.
Wednesday 2 Nov at 8-10 in room D35.
Monday 7 Nov at 8-10 in room L31.
Wednesday 9 Nov at 8-10 in room L31.
Monday 14 Nov at 8-10 in room L41.
Wednesday 16 Nov at 13-15 in room D33.
Monday 21 Nov at 8-10 in room L31.
Wednesday 23 Nov at 8-10 in room L31.
Monday 28 Nov at 8-10 in room L31.
Monday 5 Dec at 8-10 in room D33.
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.
Homework number three, due Monday, November 28,
2011. Hint: 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).
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 questions on the written exam will all but one be taken from the
list of study questions.
Course requirements
Written examination (3 credits); Computer assignments (4.5 credits)
