Deutsch
Help
Login
Lectures
Courses
Academic Programs
Offered Theses
Application for studies
Mobility Services
roomTUlearn
Rooms
Booking Schedule
Student Support Services
Lehre
Forschung
Organisation
101.264
AKNUM: Hierarchical Matrices and Fast Multipole Method
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.
2009S
2006W
2009S, VO, 2.0h, 3.0EC
Properties
Semester hours: 2.0
Credits: 3.0
Type: VO Lecture
Aim of course
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.
Subject of course
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.
Additional information
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.
Lecturers
Praetorius, Dirk
Institute
E101 Institute of Analysis and Scientific Computing
Course dates
Day
Time
Date
Location
Description
Wed
12:00 - 13:00
04.03.2009
Sem.R. DA grün 04
Vorbesprechung
Fri
08:30 - 10:00
06.03.2009 - 30.06.2009
Sem.R. DA grün 04
VO H-Matrizen
Show single appointments
AKNUM: Hierarchical Matrices and Fast Multipole Method - Single appointments
F
P
1
N
E
Day
Date
Time
Location
Description
Wed
04.03.2009
12:00 - 13:00
Sem.R. DA grün 04
Vorbesprechung
Fri
06.03.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
13.03.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
20.03.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
27.03.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
03.04.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
10.04.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
17.04.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
24.04.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
01.05.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
08.05.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
15.05.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
22.05.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
29.05.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
05.06.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
12.06.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
19.06.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
Fri
26.06.2009
08:30 - 10:00
Sem.R. DA grün 04
VO H-Matrizen
F
P
1
N
E
Course registration
Not necessary
Group Registration
Group
Registration From
To
VO VO Hierarchische Matrizen
01.03.2009 00:00
31.03.2009 23:59
Register in a Group
Curricula
Study Code
Obligation
Semester
Precon.
Info
066 400 Mathematics
Not specified
066 401 Statistics
Not specified
066 402 Mathematics in Science and Technology
Not specified
066 403 Mathematics in Economics
Not specified
066 404 Mathematics in Computer Science
Not specified
066 405 Financial and Actuarial Mathematics
Not specified
860 Technical Mathematics
Not specified
864 Mathematics for Natural Sciences
Not specified
866 Economic Mathematics
Not specified
867 Statistics
Not specified
869 Mathematics in Computer Science
Not specified
873 Finance and Actuarial Mathematics
Not specified
Literature
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.
Previous knowledge
Basic knowledge of analysis and linear algebra as well as of some higher programming knowledge (e.g., C, Fortran, C++ etc.) should be sufficient.
Miscellaneous
Course homepage
Language
German