Druckansicht der Internetadresse:

Faculty of Mathematics, Physics & Computer Science

Chair of Scientific Computing

Print page

Another software library on hierarchical matrices for elliptic differential equations (AHMED)

Hierarchical matrices are an efficient framework for large-scale fully populated matrices. The efficiency is based on the restriction to low-rank matrices on each block of a suitable hierarchical matrix partition. In addition to storing such matrices, approximations of the usual matrix operations can be computed with logarithmic-linear complexity for arbitrary precision, which can be exploited to setup approximate preconditioners in an efficient and convenient way.
The existing theory shows that hierarchical matrix approximations with logarithmic-linear complexity can be generated at least for discretizations of non-local operators arising in the context of elliptic boundary value problems, i.e., inverses, Schur complements, and the factors of the LU decomposition of finite element stiffness matrices. Hierarchical matrices are provably robust with respect to nonsmooth coefficients appearing in the partial differential operator.
Another field of application is boundary element methods. Here, the adaptive cross approximation method can be used to construct hierarchical matrix approximations based on few of the original matrix entries.

For more information on hierarchical matrices see the monograph.

The AHMED software library is one of the most efficient implementations of the hierarchical matrix methodology. It contains functions for the following purposes:

Matrix Partitioning
  • Visualization
  • Clustering based on
    • principal component analysis, bounding boxes (quasi-uniform grids)
    • spectral bisection using the matrix graph (general sparse matrices)
    • interface to METIS

Hierarchical Matrix Arithmetic
  • H-matrix-vector multiplication
  • H-matrix addition
  • parallel versions of the previous two operations
  • H-matrix-matrix multiplication
  • H-matrix inversion
  • H-matrix LU, LDL^T, and Cholesky factorization (also in parallel for sparse matrices)
  • adaptive and bounded rank versions
  • symmetric H-matrix arithmetic
  • single and double precision real and complex arithmetic
  • algebraic recompression methods
  • various iterative solvers

Integral Equations in 2D and 3D
  • fast approximation algorithms (ACA method)
  • nested ACA achieves linear storage complexity
  • parallel matrix approximation
  • preconditioning using H-matrix LU decomposition

Finite Element Methods
  • LU factorization of stiffness matrices
  • nested dissection reordering
  • parallel approximate LU factorization
  • approximation of Schur complements
  • efficient preconditioning using H-matrix inverse or LU decomposition

The library is written in C++. Time-critical components are based on LAPACK and BLAS. The parallel parts of the library use the MPI standard.


Webmaster: Massimo Pinzer-Braese

Facebook Twitter Youtube-Kanal Instagram Blog Contact