Hierarchical Matrices

News

Winterschool on hierarchical matrices.
The next winterschool on hierarchical matrices will take place at Kiel University from the 4th to the 8th or March, 2018. 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 H2Lib software package. Details can be found on the winterschool homepage.

H2Lib released.
The third version of the new H2Lib package has been released to the public. New features include

• Directional H²-matrices for high-frequency Helmholtz problems.
• Extended GPGPU- and SIMD-acceleration for 3D BEM.
• Lowest-order Raviart-Thomas elements for Darcy's equation with matching domain-decomposition clustering strategies.

H2Lib released.
The second version of the new H2Lib package has been released to the public. New features include

• Support for complex and single-precision types.
• Boundary element discretization for 3D Helmholtz problems.
• GPGPU-acceleration for BEM quadrature and H²-GCA compression.
• Finite element discretization for 2D and 3D problems.
• Domain-decomposition clustering.

H2Lib released.
The first release of the new H2Lib package has been made available to the public. It is closely related to HLib, but differs in a number of important points:

• H2Lib is published as free and open source software under the GNU lesser public license. It can be obtained free of charge at GitHub.
• The library offers matrix arithmetic operations (multiplication, inversion, factorization) both for hierarchical matrices and H²-matrices.
• Integral equations are supported by a wide range of optimized approximation algorithms.
• Dense matrices and vectors are represented by separate data types, allowing the library to perform, e.g., bounds checking.
• Although the library's performance benefits significantly from additional packages like LAPACK, these packages are not required.
• Online documentation is available at the project website.

Bug in HLib: Incorrect array operations when writing to a file.
The function write_supermatrix used to write a hierarchical matrix to a file computed an index with the wrong leading dimension. The problem is solved by a patch available at the HLib patches page.

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 11th to the 15th of March, 2013. The deadline for registrations is the 29th of February, 2013. 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 Book on H²-Matrices.
The first book on H²-matrix methods is now available. It offers a comprehensive introduction into the relevant algorithms, the techniques for the corresponding complexity and error analysis, and a collection of numerical examples illustrating the properties of the H²-matrix method. All algorithms presented in the book will be included in the next release HLib.

Big Book on Hierarchical Matrices.
The big book on hierarchical matrix techniques has been published. If offers an overview of the current state of the art in the field of hierarchical matrix techniques and covers topics like algebraic and analytic low-rank approximations, matrix arithmetic operations and applications to integral operators, matrix equations and preconditioning of elliptic partial differential equations.

Bug in HLib: Incorrect quadrature for two-dimensional boundary elements.
The singular quadrature routines in quadrature1d used for discretizing integral operators in curvebem relied on invalid symmetry assumptions, and the logarithmic kernel function used in curvebem was treated incorrectly in the computation of the diagonal entries of the single layer potential matrix. Both problems are solved by a patch available at the HLib patches page.

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].

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.