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.