On the accuracy of inexact saddle point solvers

For large--scale saddle point problems, the application of exact
iterative schemes and preconditioners may be computationally
expensive. In practical situations, only approximations to the
inverses of the diagonal block or the related cross-product
matrices are considered, giving rise to inexact versions of
various solvers. Therefore, the approximation effects must be
carefully studied. In this talk we study numerical behavior of
several iterative Krylov subspace solvers applied to the solution
of large-scale saddle point problems. Two main representatives of
the segregated solution approach are analyzed: the Schur
complement reduction method, based on an (iterative) elimination
of primary variables and the null-space projection method which
relies on a basis for the null-space for the constraints. We
concentrate on the question what is the best accuracy we can get
from inexact schemes solving either Schur complement system or the
null-space projected system when implemented in finite precision
arithmetic. The fact that the inner solution tolerance strongly
influences the accuracy of computed iterates is known and was
studied in several contexts.

In particular, for several mathematically equivalent
implementations we   study the influence of inexact solving the
inner systems and estimate their maximum attainable accuracy. When
considering the outer iteration process our rounding error
analysis leads to results similar to ones which can be obtained
assuming exact arithmetic. The situation is different when we look
at the residuals in the original saddle point system. We can show
that some implementations lead ultimately to residuals on the the
roundoff unit level independently of the fact that the inner
systems were solved inexactly on a much higher level than their
level of limiting accuracy. Indeed, our results confirm that the
generic and actually the cheapest implementations deliver the
approximate solutions which satisfy either the second or the first
block equation to the working accuracy. In addition, the schemes
with a corrected direct substitution are also very attractive. We
give a theoretical explanation for the behavior which was probably
observed or it is already tacitly known. The implementations that
we pointed out as optimal are actually those which are widely used
and suggested in applications.