TUHH / Institut für Mathematik / Forschungsgebiete / Hierarchical Matrix preconditioning of Saddle point problems

Hierarchical Matrix preconditioning of Saddle point problems

Working Groups: Lehrstuhl Numerische Mathematik

Collaborators (MAT): Jonas Grams, M. Sc., Prof. Dr. Sabine Le Borne

Description

Many natural phenomena can be described with systems of partial differential equations. Fluid flow problems can be modeled by the Navier-Stokes equations, and their discretization results in saddle point problems of the form \[ \begin{pmatrix} \mathbf{F} & \phantom{-}\mathbf{B}^{\mathsf{T}} \\ \mathbf{B} & -\mathbf{C}^{\phantom{T}} \end{pmatrix} \begin{pmatrix} \mathbf{u}\\\mathbf{p} \end{pmatrix} = \begin{pmatrix} \mathbf{f}\\ \mathbf{g} \end{pmatrix}. \] Typically, these systems of equations are very large and need to be solved iteratively. A good preconditioner is necessary to do this efficiently. A widely used precondition technique for saddle point problems is given by block preconditioners which rely on an approximation \(\widetilde{\mathbf F}\) to the upper left block \(\mathbf{F}\) and an approximation \(\widetilde{\mathbf S}\) of the Schur complement \(\mathbf S = - \mathbf C - \mathbf B \mathbf F^{-1} \mathbf B^{\mathsf T}\).

A key requirement for the approximations \(\widetilde{\mathbf{F}}\) and \(\widetilde{\mathbf{S}}\) is that their inverses can be applied efficiently while the approximations are still good enough to obtain a fast convergence rate for the solver.

Hierarchical matrices (\(\mathcal H\)-Matrices) are matrices with hierarchical block low-rank structure that provide a data-sparse approximation to matrices as well as fast methods for approximate LU factorization. Thus, they offer easy to invert approximations to \(\mathbf F\) and \(\mathbf S\) while the accuracy of the approximations can be controlled with the local ranks.

The approximations \(\widetilde{\mathbf F}\) and \(\widetilde{\mathbf{S}}\) can be obtained by:

  1. computing an (approximate) \(\mathcal H\)-LU factorization \(\mathbf{F} \approx \mathbf L\mathbf U = \widetilde{\mathbf F}\),
  2. computing an approximation \(\widehat{\mathbf S} = -\mathbf C - \mathbf B \mathbf U^{-1} \mathbf L^{-1}\mathbf B^{\mathsf T} = -\mathbf C - (\mathbf B \mathbf U^{-1})(\mathbf B \mathbf L^{-1})^{\mathsf T}\) to the Schur complement \(\mathbf{S}\),
  3. computing an (approximate) \(\mathcal H\)-LU factorization \(\widehat{\mathbf S} \approx \widehat{\mathbf L}\widehat{\mathbf U} = \widetilde{\mathbf S}\).

A disadvantage of this method is the time-consuming computation of the approximate Schur complement in step 2.

To speed up the computation of the product \((\mathbf B \mathbf U^{-1})(\mathbf B \mathbf L^{-1})^{\mathsf T}\) in 2., we develop the following two improvements.

First, the block structure of the hierarchical matrices has an influence on the complexity of matrix-matrix multiplications. Thus, we develop problem-tailored adjustments to the block structure which improve the complexity of the multiplication.

Second, we integrate recently introduced new approaches for the multiplication of hierarchical matrices (see [1,2]). The first article proposes a multiplication algorithm with rearranged low-rank truncation. The second article proposes an algorithm which allows for matrix-vector operations based on randomized low-rank approximations.

References

[1] S. Börm, Hierarchical matrix arithmetic with accumulated updates. Comput. Vis. Sci. 20 (2019), no. 3-6, 71–84. doi: 10.1007/s00791-019-00311-3.
[2] J. Dölz, H. Harbrecht, M. Multerer, On the best approximation of the hierarchical matrix product. SIAM J. Matrix Anal. Appl. 40 (2019), no. 1, 147–174. doi: 10.1137/18M1189373