Algebraic Multigrid (AMG) for Saddle Point Systems

Abstract

We introduce an algebraic multigrid method for the solution of matrices with saddle point structure. Such matrices e.g. arise after discretization of a second order partial differential equation (PDE) subject to linear constraints.<br /> Algebraic multigrid (AMG) methods provide optimal linear solvers for many applications in science, engineering or economics. The strength of AMG is the automatic construction of a multigrid hierarchy adapted to the linear system to be solved. However, the scope of AMG is mainly limited to symmetric positive definite matrices. An essential feature of these matrices is that they define an inner product and a norm. In AMG, matrix-dependent norms play an important role to investigate the action of the smoother, to verify approximation properties for the interpolation operator and to show convergence for the overall multigrid cycle. Furthermore, the non-singularity of all coarse grid operators in a AMG hierarchy is ensured by the positive definiteness of the initial fine level matrix.<br /> Saddle point matrices have positive and negative eigenvalues and hence are indefinite. In consequence, if conventional AMG is applied to these matrices, the method will not always converge or may even break down if a singular coarse grid operator is computed. In this thesis, we describe how to circumvent these difficulties and to build a stable saddle point AMG hierarchy. We restrict ourselves to the class of Stokes-like problems, i.e. saddle point matrices which contain a symmetric positive definite submatrix that arises from the discretization of a second order PDE.<br /> Our approach is purely algebraic, i.e. it does not require any information not contained in the matrix itself. We identify the variables associated to the positive definite submatrix block (the so-called velocity components) and compute an inexact symmetric positive Schur complement matrix for the remaining degrees of freedom (in the following called pressure components). Then, we employ classical AMG methods for these definite operators individually and obtain an interpolation operator for the velocity components and an interpolation operator for the pressure matrix.<br /> The key idea of our method is to not just merge these interpolation matrices into a single prolongation operator for the overall system, but to introduce additional couplings between velocity and pressure. The coarse level operator is computed using this "stabilized" interpolation operator. We present three different interpolation stabilization techniques, for which we show that they resulting coarse grid operator is non-singular. For one of these methods, we can prove two-grid convergence. The numerical results obtained from finite difference and finite element discretizations of saddle point PDEs demonstrate the practical applicability of our approach.