Study of block diagonal preconditioners using partial spectral information to solve linear systems arising in constrained optimization problems

Abstract

This work is concerned with the development and the study of
novel block diagonal preconditioners for solving indefinite linear systems with
a saddle - point form. We consider the « ideal » block diagonal preconditioner
proposed by Murphy, Golub and Wathen (2000) based on the exact Schur com-
plement, and we focus on the case where the (1,1) block has few very small
eigenvalues. Assuming that the exact information on these eigenvalues and
their associated eigenvectors is available, we propose different approximations
of the block diagonal preconditioner of Murphy, Golub and Wathen and we
analyse the spectral properties of the preconditioned matrices. We general-
ize the theoretical results on systems arising in interior-point methods and we
illustrate the performance of the proposed preconditioners through some nu-
merical experiments. We finally analyse the interaction between the (1,1) and
(1,2) blocks of saddle-point systems and we study the circumstances in which
small eigenvalues of the (1,1) block can have an impact on the convergence of
iterative methods.

Date of Award	11 Jul 2016
Original language	English
Awarding Institution	University of Namur
Supervisor	Annick Sartenaer (Supervisor), Dominique Orban (Jury), Daniel RUIZ (Jury), Anders Forsgren (Jury) & Anne Lemaitre (President)