Hierarchical Matrices

News

Winterschool on hierarchical matrices.
The next winterschool on hierarchical matrices will take place at the Max Planck Institute for Mathematics in the Sciences from the 17th to the 20th of March, 2008. The deadline for registrations is the 31st of January, 2008. The winterschool will focus on the theoretical foundation of hierarchical matrix techniques and on the practical implementation of the corresponding algorithms and data structures in the context of the HLib package. Details can be found on the winterschool homepage.

New Paper: Adaptive variable-rank approximation of general dense matrices.
The paper [Börm2005b] introduces a modification of the standard H²-matrix recompression algorithm presented in [Börm/Hackbusch2002] that allows it to reduce the storage requirements by using techniques introduced in the context of variable-order approximation schemes [Sauter2000].

New paper: Data-sparse approximation of non-local operators by H²-matrices.
Although any matrix can be approximated by an H²-matrix, the resulting rank may turn out to be too large for an efficient data-sparse representation. The paper [Börm2005] provides a criterion which can be used to establish upper bounds for the rank required for a given approximation accuracy and applies the criterion to classical integral operators and solution operators of elliptic partial differential equations.

Lecture notes of the winterschool on hierarchical matrices.
The lecture notes [Börm/Grasedyck/Hackbusch2004] of the winterschool on hierarchical matrices have been updated. The current version covers the application of hierarchical matrices to integral and partial differential equations, approximative arithmetics, complexity estimates and H²-matrices.

HLib 1.3 released.
The new version 1.3 of the HLib package is now available. Important new features include hybrid cross approximation of boundary element operators, improved orthogonalization and recompression routines for H²-matrices, new (and hopefully more accessible) example programs, and H²-matrix arithmetics in linear complexity.

New paper: Hybrid cross approximation of integral operators.
A popular approach to constructing low-rank approximations of discretized integral operators is based on the application of cross approximation techniques [Tyrtyshnikov2000], [Bebendorf/Rjasanow2003] to entries of the discrete matrix. This has the advantage that a complete H-matrix approximation can be created based only on a routine for evaluating integrals and some geometric information. Unfortunately, this approach can be shown to fail in a number of important situations, e.g., for the classical double layer operator on polygonal domains. This is due to the fact that too much information is lost in the transition from the continuous to the discrete problem. The paper [Börm/Grasedyck2004] proposes a different approach: the cross approximation is applied to the original kernel function, and the resulting kernel expansion is then discretized. Numerical experiments indicate that this hybrid technique is both faster and more reliable than previous methods.

New paper: Adaptive cluster bases for H²-matrices.
Cluster bases created by simple interpolation or Taylor expansion are typically not optimal for the approximation of integral operators. Different methods can be used to optimize cluster bases: A variant of Gram-Schmidt orthogonalization can be used to remove redundant functions directly, and a variant of the compression algorithm described in [Börm/Hackbusch2002] can be applied to find bases that are almost optimally adapted to the geometry, the discretization and the kernel function. The algorithms and the corresponding error analysis can be found in [Börm2004].

New paper: Efficient addition and multiplication of H²-matrices.
One of the major advantages of H-matrices, as compared to other data-sparse formats, is the possibility of performing arithmetic operations like matrix addition and multiplication efficiently, i.e., in almost linear complexity. For H²-matrices, the new paper [Börm2004a] presents algorithms for the computation of matrix sums and products in true linear complexity, i.e., the best approximation of the sum or product of two n-dimensional H²-matrices is computed in O(n) operations.