Efficient Preconditioners for PDE-Constrained Optimization Problems with a Multi-level Sequentially Semi-Separable Matrix Structure

In this paper, we consider preconditioning for PDE-constrained optimization problems. The underlying problems yield a linear saddle-point system. We study a class of preconditioners based on multilevel sequentially semiseparable (MSSS) matrix computations. The novel global preconditioner is to make use of the global structure of the saddle-point system, while the block preconditioner makes use of the block structure of the saddle-point system. For the novel global preconditioner, it is independent of the regularization parameter, while for the block preconditioner, this property does not hold. For this MSSS matrix computation approach, model order reduction algorithms are essential to obtain a low computational complexity. We study two different model order reduction approaches, one is the new approximate balanced truncation algorithm with low-rank approximated Gramians and the other is the standard Hankel blocks approximation algorithm. We test the global preconditioner and the block preconditioner for the problem of optimal control of the Poisson equation and optimal control of the convection-diffusion equation. Numerical experiments illustrate that both preconditioners give linear computational complexity and the global preconditioner yields the fewest number of iterations and computing time. Moreover, the approximate balanced truncation algorithm consumes less floating-point operations (flops) than the Hankel blocks approximation algorithm