NUMERICAL SOLUTION OF SADDLE POINT PROBLEMS BY PROJECTION
Abstract
In this thesis, we work on iterative solutions of large linear systems of saddle
point problems of the form
A B1
T
B2 0
x
y
=
f
0
,
where A ∈ R
n×n
, B1, B2 ∈ R
m×n
, f ∈ R
n
, and n ≥ m. Many applications in
computational sciences and engineering give rise to saddle point problems such as
finite element approximations to Stokes problems, image reconstruction, tomography,
genetics, statistics and model order reduction for dynamical systems. Such problems
are typically large and sparse.
We develop new techniques to solve the saddle point problems depending on the
rank of B2. First, we deal with the case when B2 has full row rank, i.e., rank(B2) = m.
The key idea is to construct a projection matrix and transform the original problem
to a least squares problem then solve the least squares problem by using one of the
iterative methods such as LSMR. In most applications B2 has full rank, but not
always. Next, we turn to the saddle point systems with the rank-deficient matrix B2. Similarly we construct a new projection matrix by using only maximal linearly
independent rows of B2. By using this projection matrix, the original problem can
still be transformed into a least squares problem. Again, the new system can be
solved by using one of the iterative techniques for least squares problems. Numerical
experiments show that the new iterative solution techniques work very well for large
sparse saddle point systems with both full rank and rank-deficient matrix B2.