Why using Htool?

Htool aims to provide matrix compression via parallelized hierarchical matrices, and in particular, it provides

  • parallel matrix-vector and matrix-matrix product using MPI and OpenMP,

  • iterative solvers via HPDDM,

  • preconditioning techniques using domain decomposition methods.

Why?

The storage and cost of assembly for dense matrices are both quadratic with respect to their size, while the cost of using linear solvers is cubic for direct solvers. For iterative solvers, the matrix-vector product has quadratic complexity, which is to be multiplied by the number of iterations. To reduce these costs, several compression techniques have been developed, which gives approximated representation of matrix-vector product and other operations. Htool provides compression via Hierarchical matrices, and emphasize has been put on

  • parallelisation for high-performance computing,

  • a black box interface, to tackle a great variety of problems.

Applications

Hierarchical matrices are generally used to compress matrices stemming from the discretisation of asymptotically smooth kernels \(\kappa (x,y)\), i.e, for two cluster of geometric points \(X\) and \(Y\),

\[\rvert \partial_x^{\alpha} \partial_y^{\beta}\kappa (x,y)\lvert \leq C_{\mathrm{as}}\lvert x - y\rvert^{-\lvert \alpha \rvert -\lvert \beta \rvert - s}.\]

with \(x\in X\), \(y\in Y\), \(x\neq y\), \(\alpha, \beta \in \mathbb{N}_0^d\) and \(\alpha+\beta \neq 0\).

Such matrices arise in the context of

  • discretisation of boundary integral equations 1,

  • solving Lyapunov and Riccati equations 1,

  • discretization of the integral Fractional laplacian 2,

  • kernel-based scattered data interpolation 3.

1(1,2)

Steffen Börm, Lars Grasedyck, and Wolfgang Hackbusch. Introduction to hierarchical matrices with applications. Engineering Analysis with Boundary Elements, 27(5):405–422, 2003.

2

Mark Ainsworth and Christian Glusa. Towards an efficient finite element method for the integral fractional laplacian on polygonal domains. In Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan, pages 17–57. Springer International Publishing, 2018. doi:10.1007/978-3-319-72456-0_2.

3

Armin Iske, Sabine Le Borne, and Michael Wende. Hierarchical matrix approximation for kernel-based scattered data interpolation. SIAM Journal on Scientific Computing, 39(5):A2287–A2316, jan 2017. doi:10.1137/16m1101167.