Hierarchical matrix
In numerical mathematics, hierarchical matrices (H-matrices) are used as data-sparse approximations of non-sparse matrices.
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In numerical mathematics, hierarchical matrices (H-matrices) are used as data-sparse approximations of non-sparse matrices. While a sparse matrix of dimension n can be represented efficiently in O(n) units of storage by storing only its non-zero entries, a non-sparse matrix would require O(n^2) units of storage, and using this type of matrices for large problems would therefore be prohibitively expensive in terms of storage and computing time.
Hierarchical matrices provide an approximation requiring only O(n k\,\log(n)) units of storage, where k is a parameter controlling the accuracy of the approximation. In typical applications, e.g., when discretizing integral equations, preconditioning the resulting systems of linear equations, or solving elliptic partial differential equations, a rank proportional to \log(1/\epsilon)^\gamma with a small constant \gamma is sufficient to ensure an accuracy of \epsilon .
Compared to many other data-sparse representations of non-sparse matrices, hierarchical matrices offer a major advantage: the results of matrix arithmetic operations like matrix multiplication, factorization or inversion can be approximated in O(n k^\alpha\,\log(n)^\beta) operations, where \alpha,\beta\in\{1,2,3\}. {\mathcal G}[u](x) = \int_\Omega \kappa(x,y) u(y) \,dy. The Galerkin method leads to matrix entries of the form g_{ij} = \int_\Omega \int_\Omega \kappa(x,y) \varphi_i(x) \psi_j(y) \,dy\,dx, where (\varphi_i)_{i\in I} and (\psi_j)_{j\in J} are families of finite element basis functions.
If the kernel function \kappa is sufficiently smooth, we can approximate it by polynomial interpolation to obtain \tilde\kappa(x,y) = \sum_{\nu=1}^k \kappa(x,\xi_\nu) \ell_\nu(y), where (\xi_\nu)_{\nu=1}^k is the family of interpolation points and (\ell_\nu)_{\nu=1}^k is the corresponding family of Lagrange polynomials. Replacing \kappa by \tilde\kappa yields an approximation \tilde g_{ij} = \int_\Omega \int_\Omega \tilde\kappa(x,y) \varphi_i(x) \psi_j(y) \,dy\,dx = \sum_{\nu=1}^k \int_\Omega \kappa(x,\xi_\nu) \varphi_i(x) \,dx \int_\Omega \ell_\nu(y) \psi_j(y) \,dy = \sum_{\nu=1}^k a_{i\nu} b_{j\nu} with the coefficients a_{i\nu} = \int_\Omega \kappa(x,\xi_\nu) \varphi_i(x) \,dx, b_{j\nu} = \int_\Omega \ell_\nu(y) \psi_j(y) \,dy.
If we choose t\subseteq I,s\subseteq J and use the same interpolation points for all i\in t,j\in s , we obtain G|_{t\times s} \approx A B^* . Obviously, any other approximation separating the variables x and y , e.g., the multipole expansion, would also allow us to split the double integral into two single integrals and thus arrive at a similar factorized low-rank matrix.
Of particular interest are cross approximation techniques that use only the entries of the original matrix G to construct a low-rank approximation. The central algorithm is the efficient matrix-matrix multiplication, i.e., the computation of Z = Z + \alpha X Y for hierarchical matrices X,Y,Z and a scalar factor \alpha .
The algorithm requires the submatrices of the hierarchical matrices to be organized in a block tree structure and takes advantage of the properties of factorized low-rank matrices to compute the updated Z in O(n k^2\,\log(n)^2) operations. Taking advantage of the block structure, the inverse can be computed by using recursion to compute inverses and Schur complements of diagonal blocks and combining both using the matrix-matrix multiplication.
In a similar way, the LU decomposition can be constructed using only recursion and multiplication. Both operations also require O(n k^2\,\log(n)^2) operations.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1285634482 under CC BY-SA 4.0; modifications have been made.