Features

Clustering is the first step towards an H-matrix and defines a hierarchical decomposition of the given set of unknowns.

Geometrical clustering uses available spatial information, e.g. coordinates, for each index to decompose the index set. A standard algorithm is binary space partitioning, where the coordinates are geometrically decomposed by a hyperplane in each step of the algorithm. Several variants exists, which choose the dividing hyperplane differently:

• geometrically balanced, e.g. maintain equal volume per sub cluster
• cardinality balanced, e.g. maintain equal number of indices per sub cluster
• principal component analysis

In case of a sparse matrix without geometric information for each index, a clustering method based on the connectivity information in the matrix is available. HLIBpro implements two algorithms based on breath-first-search and multi-level graph partitioning, combined with partitioning optimisation. Furthermore, HLIBpro supports external graph partitioning libraries (Mongoose, METIS, SCOTCH)

In the case of sparse matrices, geometrically neighboured domains can be separated via nested dissection. Applied to clustering, the generated H-matrix has many large, empty off-diagonal matrix blocks which remain zero during matrix factorisation. This significantly improves memory and computational complexity and can be used with geometrical as well as algebraic clustering.

Many applications have an internal block-structure, e.g. where the x-, y- and z-components are treated individually, that is unknown or hard to detect for HLIBpro. For such cases, a user defined partitioning may be provided, separating the indices in a first step and then appling the standard clustering techniques, e.g. geomtrical or cardinality based clustering. In the same way, it is also possible to enforce individual indices to stick together, e.g. they will never be split during clustering.

Matrix construction is implemented for dense and sparse matrices. While in the latter case the matrix coefficients only need to be copied into the new H-matrix, dense matrices require approximation techniques to maintain linear complexity. Two major methods are available in HLIBpro: adaptive and hybrid cross approximation. Mainly for comparative purposes, also singular value decomposition is implemented, which gives the best approximation but comes with \(\mathcal{O}(n^3)\) complexity.

During matrix construction, neighboured matrix blocks may be joined together provided that the joined block uses less memory while still maintaining the same approximation. This is called coarsening and may reduce the memory requirements drastically.

ACA is a heuristical approach, which successively constructs rank-1 updates based on the magnitude of the matrix coefficients. HLIBpro implements the original ACA algorithm as well as an improved version (ACA+), known to work on a broader range of matrices.

For ACA and ACA+ only the matrix coefficients of the dense matrix are neccessary. These are supplied in the form of a coefficient function by the user. That way, only \(\mathcal{O}(n \log n)\) many coefficients are needed, which greatly reduces the computational complexity.

HCA avoids the problems of ACA and is proven to yield an approximatation up to a given accuracy. For this, the matrix coefficients as well as simple integrals (collocation integrals of the generating function of the kernel) have to be supplied by the user. The complexity is again in \(\mathcal{O}(n \log n)\) and in many cases, especially for larger problems better than ACA/ACA+.

The standard algebra includes matrix-vector multiplication, matrix addition and matrix multiplication. These algorithms are available for shared and distributed memory systems (except matrix multiplication).

HLIBpro implements matrix inversion and various matrix factorisation techniques, e.g. LU, LDU, LL, LDL and WAZ factorisation. These algorithms are implemented for shared systems only.

Together with the matrix factorisation, the corresponding matrix solve methods for triangular (H-) matrices are available.

HLIBpro furthermore, contains functions for computing the Frobenius and the spectral norm of matrices (and their difference, e.g. \(A-B\)). In the case of the spectral norm, one may also compute the approximation with respect to the inverse of a matrix, e.g. \(\|I-B·A\|_2\) where B is the approximate inverse of A. This allows to check the quality of H-factorisation or inversion for solving or preconditioning.

H²-matrices are a special version of H-matrices with an even more compact representation. HLIBpro implements the construction of cluster bases and the conversion of H-matrices to H²-matrices.

HLIBpro contains a complete application layer for boundary element methods. It is based on triangular surface grids and provides various function spaces, e.g. piecewise constant and linear as well as edge spaces. Furthermore, bilinear forms for Laplace SLP/DLP, Helmholtz SLP/DLP, Maxwell EFIE/MFIE, acoustic scattering and exponential kernel are provided. Optimised implementations of these kernels using SSE3, AVX, AVX2, AVX512 and MIC vector operations are available.

Iterative algorithms for solving linear equation systems with or without preconditioning are part of HLIBpro:

• Richardson iteration
• CG, CGS and BiCG-Stab iteration
• MINRES and GMRES iteration
• TFQMR iteration

HLIBpro supports several standard file-formats for matrices, vectors and triangular surface grids.

• HLIBpro format
  • support for H-, sparse and dense matrices
  • support for dense vectors
  • support for cluster bases
  • support for triangle grids
• SAMG
  • support for sparse matrices and dense vectors
• Matlab
  • support for sparse and dense matrices and vectors (possibly in structs)
  • compression supported with zlib
• Harwell-Boeing/Rutherford and MatrixMarket
• HDF5 format for dense and low-rank matrices
• Ply, SurfaceMesh and GMSH v2 file format for grids

Cluster trees, block cluster trees, matrices, coordinates, grids and grid functions (BEM) may also be visualised in PostScript, PDF and VTK (for 3D data) file format, providing various options to modify the output and to display only the interesting information.