Zurich Summer School

Title / Abstract

Hierarchical matrices

Hierarchical matrices offer an elegant approach to treating non-local operators arising, e.g., in integral equations or as solution operators of elliptic partial differential equations. Similar to panel clustering and multipole methods, they split a matrix into sub-matrices of low numerical rank that can be approximated efficiently in factorized form. This factorized low-rank representation can be either derived by analytical means, e.g., by approximation a kernel function using tensor products, or by algebraic means, e.g., by computing the singular value decomposition of the sub-matrix. The latter approach gives rise to efficient algorithms for approximating the product, the inverse or the LR factorization of a hierarchical matrix. Applications include the discretization of integral equations, the construction of robust preconditioners for partial differential equations and solution schemes for matrix equations arising in the context of control theory.

Lectures

Lecture 1: Introduction to hierarchical matrices

one-dimensional model problem
error and complexity estimates
implementation and basic data structures

Lecture 2: Hierarchical matrices for multi-dimensional problems

general cluster and block trees,
application to boundary element methods

Lecture 3: H-matrix preconditioners

low-rank truncation
approximate matrix operations

Lecture 4: H²-matrices

cluster bases
forward and backward transformation

Lecture 5: Advanced techniques

H²-matrix operations
approximation of boundary element matrices by quadrature

Lecture Slides

Lecture Slides from Aug 18

Lecture Slides Part 1 from Aug 19
Lecture Slides Part 2 from Aug 19
Lecture Slides Part 3 from Aug 19
Lecture Slides Part 4 from Aug 20
Lecture Slides Part 5 from Aug 21

Exercises

Theoretical Exercises from Aug 19
Practical Exercises from Aug 19
Exercises 3 from Aug 21
Exercises 4 from Aug 21

Software

The H-matrix library HLib is available free of charge for research purposes. It includes a collection of simple exercises for several typical applications of H- and H²-matrices.

Literature

The lecture notes of the winter school on hierarchical matrices offer an introduction to the basic concepts of hierarchical matrix techniques and the data structures used in the HLib package. The following research papers and books are also recommended:

Wolfgang Hackbusch
"A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices", Computing (1999), 62:89-108
Wolfgang Hackbusch, Boris Khoromskij
"A sparse matrix arithmetic based on H-matrices. Part II: Application to multi-dimensional problems", Computing (2000), 64:21-47
Wolfgang Hackbusch, Boris Khoromskij, Stefan Sauter
"On H²-matrices", Lectures on Applied Mathematics (2002), page 9-29, Springer Berlin
Steffen Börm, Wolfgang Hackbusch
"Data-sparse approximation by adaptive H²-matrices", Computing (2002), 69:1-35
Lars Grasedyck, Wolfgang Hackbusch
"Construction and arithmetics of H-matrices", Computing (2003), 70:295-334
Mario Bebendorf, Sergej Rjasanow
"Adaptive low-rank approximation of collocation matrices", Computing (2003), 70:1-24
Wolfgang Hackbusch
"Hierarchische Matrizen: Algorithmen und Analysis", Springer 2009
Steffen Börm
"Efficient numerical methods for non-local operators: H²-matrix compression, algorithms and analysis",EMS 2010