NUMERICAL SOLUTION OF SADDLE POINT PROBLEMS BY PROJECTION

Author

Gul Karaduman

Graduation Semester and Year

2017

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Mathematics

Department

Mathematics

First Advisor

Ren-Cang Li

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.

Keywords

Saddle point problems, KKT, Iterative

Disciplines

Mathematics | Physical Sciences and Mathematics

License

This work is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 4.0 International License.

Comments

Degree granted by The University of Texas at Arlington

Recommended Citation

Karaduman, Gul, "NUMERICAL SOLUTION OF SADDLE POINT PROBLEMS BY PROJECTION" (2017). Mathematics Dissertations. 215.
https://mavmatrix.uta.edu/math_dissertations/215