The aim of the lecture is to give an introduction to a very active field of research in numerical analysis. The Fast Multipole Method (FMM) is one of the most important algorithms in scientific computing, and it is, however, quite elementary. The lecture may yield a basis for a bachelor or diploma thesis.

The FMM has been developed by Greengard and Rokhlin (Yale University) in 1987. This algorithm allows the assembling, the storage, and the matrix-vector multiplication of (certain and practically important) dense N x N matrices in linear complexity O(N). Naive realization of which would lead to a storage requirement of N^2 and O(N^2) arithmetic operations to perform the matrix-vector multiplication. The SIAM news proclaimed the FMM to be one of the Top 10 Algorithms in numerics. In 1999, Hackbusch (Max-Planck-Institute Leipzig) introduced a matrix-version of the FMM. With the mathematical definition of "Hierarchical Matrices" (H-matrix) he provided an abstract framework for working with FMM matrices. By others, he and his co-workers provided algorithms to perform the addition, multiplication, inversion, computation of the LU decomposition etc. in almost linear complexity O(N log N). The lecture provides an introduction and overview over the most important algorithms in this field. We prove and analyse the algorithms, where emphasis is put on the complexity estimates. We also show recent results from 2005/06, e.g. the addition and multiplication of H^2 matrices in linear complexity O(N). To follow the lecture, the participants just need basic knowledge on mathematics as well as some knowledge of a higher programming language.

There is the possibility to do some practical exercises on the FMM within a 5- or 10-hour lab. There, the aim is to develop an efficient implementation of the FMM in C++. By wish of the participants (or even by necessity), the lecture can be held in English.

Lecture notes for this course are available. For major parts of the lecture, we will provide (free) lecture notes. Complete lecture notes shall be developed throughout the term and are then handed-out to the participants.

Basic knowledge of analysis and linear algebra as well as of some higher programming knowledge (e.g., C, Fortran, C++ etc.) should be sufficient.