Hierarchical matrices. A means to efficiently solve elliptic boundary value problems (Q924873): Difference between revisions

Hierarchical matrices (\(\mathcal H\)-matrices for shortness) are non-sparse matrices which are partitioned into submatrices of low-rank matrices. They allow a representation by a smaller set of data and also fast computations of matrix-vector products and of approximate inverses. Therefore not only multigrid methods provide fast solutions of elliptic partial deifferential equations, but \(\mathcal H\)-matrices are a competing tool. The first chapter is concerned with low-rank matrices and matrix partitioning. A matrix \(A\) of rank \(k\) may be represented in the form \(A = UV^H\) where \(U\) and \(V\) have \(k\) columns. Since this class of matrices is not closed under the usual procedures of linear algebra, the approximation of a given matrix by a matrix of rank \(k\) is considered. The decomposition of full matrices into blocks of low-rank matrices yields an \(\mathcal H\)-matrix if the recursive decomposition is associated to a tree called cluster tree. The latter class of trees is introduced and investigated. Chapter 2 is devoted to the addition, the LU-decomposition, and other procedures of numerical linear algebra with \(\mathcal H\)-matrices. It includes exact and approximate procedures as well as their parallelization. Chapter 3 deals with the approximation of discrete integral operators that result from boundary integral equations. Good approximation properties are expected due to smoothness of the kernel functions. Special attention is given to adaptive cross approximation, i.e., a topic of the author's research. Chapter 4 on the application to finite element discretizations starts with a discussion of the inverses of banded matrices. The theory has shown the referee why \(\mathcal H\)-matrices are so successful although it is not stated in this way. Consider for the moment a boundary value problem in 1D. The discretization leads here to a banded matrix. There is an observation which may be traced back to Asplund, Krein and others and is now covered by the theory of semiseparable matrices. The upper diagonal part and the lower diagonal part of the inverse can be represented by matrices whose ranks are not greater than the bandwith. (Moreover, there is an exponential decay if the condition number is bounded as it is with mass matrices.) Therefore, the inverse of a banded matrix is an \(\mathcal H\)-matrix with \(O(n \log n)\) blocks. When we proceed to partial differential equations (PDEs) in 2D or 3D, we have no longer the nice ordering as in 1D, but due to its generality, the concept of \(\mathcal H\)-matrices admits still the approximations by matrices of this type. Readers who are familiar only with other fast solvers of elliptic PDEs, find here a theory with very different ideas. They have to accept that many definitions are given in a formal way in this text, but then they encounter an interesting theory with applications to the fast solution of PDEs. Here the algebraic structure of the matrices is more important than the influence of the coefficients of the underlying elliptic equation.