Fast solvers for heterogeneous saddle point problems (C-SE12)



Prof. Dr. Carsten Gräser, Xingjian Zhang

Financial support:

This research is carried out in the framework of Matheon supported by Einstein Foundation Berlin


Jun 01, 2014 — May 31, 2017


The aim of this project is to develop fast solvers for heterogeneous linear saddle point problems as appearing during the iterative solution of non-smooth optimization problems, e.g., in the context of phase field models. While the development of nonlinear solvers for phase field models has reached a certain maturity, the existing solvers for the linear subproblems are still unsatisfactory. As a first step, we focus on two-phase models. Later, we plan to extend these solvers for multiphase systems.


Large scale nonsmooth nonlinear saddle point problems occur, e.g., in the context of 4th order phase field models or optimal control problems for partial differential equations. Semi-smooth or nonsmooth Newton methods have shown to be highly efficient for the iterative solution of such problems. These methods can typically be viewed as active set type strategies that lead to large linear saddle point problems as subproblems. Resulting from these active-set strategies, the subproblems are typically constrained to subsets of the domain for the primal equation. As a consequence, they can be viewed as hybrid problems that have saddle point structure only in some part of the domain, while they are elliptic in other parts. Another feature of these problems is, that they can be viewed as singularly perturbed problems, because they typically depend on small parameters, resulting, e.g., from the interface thickness in the phase field model or the regularization parameter in an optimal control problem.

While there has been significant progress on the development of fast solvers for nonsmooth nonlinear saddle point problems, the efficient solution of the resulting hybrid linear saddle point subproblems has seen far less progress. E.g., in the context of phase field problems, classical multigrid methods typically lack robustness with respect to the subdomain. As a consequence the solution of such hybrid saddle point problems is the bottle neck in real simulations of application projects.

The project aim is to support application projects by closing this gap and developing efficient solvers for those subproblems. We are especially in cooperation with the Helmholtz Virtual Institute „Microstructure control for thin film solar cells“ (HVI) where highly efficient numerical methods are crucial for the carried out simulations.


Because the known nonlinear solvers turned out to lack efficiency for the problems considered in subprojekt 6 of the HVI we extended the nonsmooth Schur-Newton method to the nonsmooth nonlinear saddle point problems with simplex constraints in cooperation with this project. The developed method exhibits mesh independent convergence and allows to solve the multi-component phase field problems considered in the HVI very efficiently (2). Since the method is a dual minimization method it leads to primal minimization problems with simplex constraints. However, such problems can be solved with multigrid efficiency using the TNNMG method (5).

Figure: Nonsmooth Schur-Newton steps over mesh size for a multi-component Penrose-Fife model and result of an LPC simulation based on the Penrose-Fife model.:

 Image Credit: Max Kahnt

 Internal Cooperations:

External Cooperations:

Project Publications:

(1) Gräser, C. and Kornhuber, R. and Sack, U. (2014) Numerical simulation of coarsening in binary solder alloys. Numerical simulation of coarsening in binary solder alloys, 93 . pp. 221-233. ISSN 09270256

(2) Gräser, C. and Kahnt, M. and Kornhuber, R. (2016) Numerical approximation of multi-phase Penrose-Fife systems. Computational Methods in Applied Mathematics, 16 (4). pp. 523-542. ISSN Online: 1609-9389, Print: 1609-4840

(3) Blatt, M. and Burchardt, A. and Dedner, A. and Engwer, C. and Fahlke, J. and Flemisch, B. and Gersbacher, C. and Gräser, C. and Gruber, F. and Grüninger, C. and Kempf, D. and Klöfkorn, R. and Malkmus, T. and Müthing, S. and Nolte, M. and Piatkowski, M. and Sander, O. (2016) The Distributed and Unified Numerics Environment, Version 2.4. Archive of Numerical Software, 4 (100). pp. 13-29. ISSN 2197-8263

(4) Engwer, C. and Gräser, C. and Müthing, S. and Sander, O. (2017) The interface for functions in the dune-functions module. Archive of Numerical Software, 5 (1). pp. 95-110. ISSN 2197-8263

Other Publications:

(5) Gräser, C. and Sander, O. (2014) Truncated nonsmooth Newton multigrid methods for simplex-constrained minimization problems. Preprint 384, IGPM Aachen . (Submitted)


04/05/2016: Nonlinearly preconditioned inexact Newton methods for nonsmooth optimization, Colloque de mathématiques, University of Geneva
09/28/2015: Type-erased interfaces in dune-functions, Dune user meeting, Heidelberg
07/08/2015: Nonsmooth Schur--Newton methods for nonsmooth saddle point problems, International Conference on Domain Decomposition Methods, Jeju Island, Korea
04/27/2015: Multigrid for block-structured nonsmooth problems, Workshop: Long running trends and upcoming traditions in the numerical treatment of PDEs, Berlin
07/10/2014: Efficient solution of nonsmooth multicomponent phase field models, AIMS Conference on Dynamical Systems, Differential Equations and Applications 2014, Madrid
09/09/2014: Truncated nonsmooth Newton multigrid methods for vector valued minimization problems* EMG 2014, Leuven


We contribute to the development of the Dune software library for highly efficient grid based methods for PDEs which especially incorporates the following dune modules:

  • Core modules: Infrastructure, FE grids, and linear algebra. The project head was the release manager of the 2.4 release (3).
  • Dune-Fufem: A simple and flexible discretization framework
  • Dune-Functions: This is a joint effort with developers of the PDELab framework to develop a simple to use common interface for FE functions (4) and highly efficents FE function space bases with a special emphasis on product spaces
  • Dune-Solvers: A general framework for iterative algebraic solvers
  • Dune-Tnnmg: An implemenation of the TNNMG method for various problem classes