Numerical Solution Of Large Sparse Linear Systems With Saddle Point Structure

Many issues involving in scienti?c and engineering computing, such as the incompressible Stokes equations, PDE-constrained optimization problems, electromagnetic problems and least squares problems, yield large sparse linear systems with saddle point structure after discretizations. Since the solving of large-scale linear algebraic equations is always one of the main concern of scienti?c calculation, we propose a series of speci?c iteration methods and preconditioning techniques to solve saddle point problems emerging in the incompressible Stokes equations, PDE-constrained optimization and hybrid formulation of time-harmonic eddy current models.The thesis is composed of ?ve chapters. Chapter 1 elaborately illustrates the background, research signi?cance, current research status and basic methods for solving the involved problems, and concisely introduced the main tasks and innovative points.Chapter 2 is divided into four sections. In Section one, we propose a method named as lopsided alternating direction(LAD) iteration and get the corresponding preconditioner for the generalized saddle point systems with a special(2, 2)–block matrix C. The convergence conditions of the LAD iteration method are given, and the eigenvalues distribution of the corresponding preconditioned matrix are analysed at the same time. Finally, numerical implementations show that the resulting LAD preconditioner leads to fast convergence when it is used to precondition Krylov subspace methods such as GMRES. In Section two, the concentration is on the generalized saddle point systems with the(2, 2)–block matrix C symmetric positive semi-de?nite. To begin with, we construct a double-parameter positive stable and semi-de?nite splitting(DPSS) iteration method, based on which, the convergence condition of the DPSS iteration method is provided. Secondly, a relaxed DPSS(RDPSS) preconditioner is proposed by relaxing the preconditioner yielded by the DPSS iteration method, and the eigenvalue distribution of the RDPSS preconditioned matrix are studied. Furthermore, the degree of the minimal polynomial of the RDPSS preconditioned matrix is given and the maximum iterative step of RDPSS preconditioned Krylov subspace method are discussed. At last, numerical experiment con?rms the high e?ciency of the RDPSS preconditioner when solving the incompressible Stokes problem. In Section three, we construct a simpli?ed RPSS(SRPSS) preconditioner to solve and precondition a class of block 2 × 2 linear systems arising from the complex symmetric inde?nite linear system. The spectral properties of the SRPSS preconditioned matrix are analysed. Numerical experiments show that the SRPSS preconditioner can be quite competitive when it is used to precondition Krylov subspace methods such as GMRES. Chapter 2 is concluded in Section four.Chapter 3 is divided into four sections as well. In Section one, we propose the BS and BLT preconditioners for the block 3 × 3 linear system arising from the Possion PDE-constrained optimization problem. The eigenvalues and corresponding eigenvectors of block preconditioned matrices are derived, respectively. Numerical experiments show that BS and BLT preconditioners can be quite competitive when the regularization parameter is small. In Section two, a block alternating splitting(BAS) iteration method is proposed to the block 2×2 complex linear systems arising from the parabolic PDE-constrained optimization problem. The convergence theory and the spectral properties of the BAS iteration method are discussed. Numerical experiments are presented to illustrate the validity of the BAS iteration as a solver as well as a preconditioner for Krylov subspace methods. Section three is a consecutive research of Section two. Firstly, we propose a parameterized block diagonal preconditioner, and give the optimal relaxation parameter expression such that ratio of absolute values of the maximum and minimum eigenvalues of the block-diagonal preconditioned matrix achieves its minimum. Secondly, we propose a block triangular preconditioner with an approximated Schur complement matrix. Spectral analyses of the block triangular preconditioned matrix are given. The eigenvalues of the block triangular preconditioned matrix are located in(12, 1] by the optimal relaxation parameter. Numerical experiments illustrate the feasibility and e?ectiveness of these preconditioners to accelerate Krylov subspace methods. Section four draws a conclusion of this chapter.In Chapter 4, a modi?ed relaxed dimensional factorization(MRDF) preconditioner in terms of the saddle point problem arising from the ?nite element discretization of the hybrid formulation of the time-harmonic eddy current problem is proposed. The convergence conditions of the corresponding MRDF iteration method are provided,and the eigenvalue distribution of the MRDF preconditioned matrix are discussed.Experimental results via a simple topology are given to show the feasibility and e?ectiveness of the MRDF preconditioner to accelerate Krylov subspace methods such as GMRES.Chapter 5 contains a summary of the whole thesis and future research directions,which focus on the optimal parameters and PDE-constrained optimization problems.