Numerical Solutions For Solving Saddle Point And Toeplitz Structured Linear Systems

Large-scale linear(algebraic) systems arise from a wide variety of applications in computational science and engineering fields, such as computational fluid dynamics,computational electromagnetic, constrained optimization, digital image processing,numerical approximations of PDEs and so on. The solution for solving linear systems plays a vital role to solve practical problems, numerical solution of linear systems is a central task in scientific and engineering computing, and is of great both theoretical and practical significance. Facing the different structures of linear systems in practical problems, how to obtain stable and efficient numerical methods by taking full advantage of special structures is an important aspect of modern numerical computation and a research focus of the numerical scientists.This thesis aims at numerical solutions for solving the structured linear systems originated in numerical discretization of differential equation, pays attention to the saddle point and Toeplitz structure of its coefficient matrix, deeply study the direct methods, matrix splitting iterations, Krylov subspace methods and preconditioning techniques for solving the liner systems, and some new iteration methods and preconditioners are presented. This thesis includes seven chapters.In Chapter 1, the background and motivations of this thesis are introduced, and the current research situation are also reviewed. The main contents, results and innovations of this thesis are given in the end of this chapter.In Chapter 2, numerical methods for solving the non-Hermitian saddle point problems are investigated. Firstly, The specific structures of two small dimensional linear systems originated in decoupling saddle point problem are separately discussed.Secondly, based on the Hermitian and skew-Hermitian splitting(HSS) of the(1, 1)-block, a new decoupled iterative method based on HSS is proposed for solving the non-Hermitian saddle point problems. The new method can improve the computational efficiency by reducing the dimension of linear systems and using the matrix splitting iterative technique. Theoretical analysis shows the proposed iterative method is convergent. Finally, numerical experiments are provided to show that the new iterative method is effective and robust.In Chapter 3, the generalized local Hermitian and skew-Hermitian splitting(GLHSS)iterative method is extended to solve the block 2 × 2 linear system, where the(1, 2)-block is not equal to the transpose of the(2, 1)-block or the(2, 2)-block is non-zero.The selections of iterative parameter matrices are discussed and the influence of the iterative parameter matrices on the computational efficiency are also considered. With different choices of the parameter matrices, the existing methods are included(e.g., local Hermitian and skew-Hermitian splitting iteration(LHSS), modify LHSS(MLHSS)and et al.), and the new methods for solving the block 2 × 2 linear systems are obtained. Theoretical analysis shows the proposed iterative methods are convergent.Numerical experiments are provided to show that the proposed methods are feasible and effective.In Chapter 4, numerical solutions of the discretized linear systems arising in the numerical discretization of partial differential equation are considered. Taking advantage of the Toeplitz and saddle point structures, a local circulant and residue splitting(LCRS) iterative method is proposed to solve Toeplitz-structured saddle point problems. Further, the splitting matrix serve as a preconditioner to accelerate the convergence rate of Krylov subspace method such as GMRES is considered. The circulant matrix can be diagonalized and the matrix-vector products can also be computed by fast Fourier transformation, which can save the amount of the calculation and improve the computational efficiency. The convergence theorem is established under suitable conditions. Numerical experiments are presented to show that the LCRS is used as either solver or preconditioner to GMRES method often outperform other tested methods in the elapsed CPU time.In Chapter 5, numerical solutions of Toeplitz structured linear systems arising in the classical Crank-Nicholson finite difference discretization of fractional diffusion equation are considered. Based on the basic idea of banded preconditioner presented by Lin(2014), by making use of the Toeplitz-like structure of spatial discretized matrices and the relevant properties, two preconditioners based on Strang and T. Chan's circulant approximation are used to accelerate conjugated gradient normal residual(CGNR) and GMRES methods for solving the resulting linear systems. The preconditioners are invertible when nonnegative diffusion coefficients, and the spectrum of the preconditioned matrices are proven to cluster around 1 when the diffusion coefficient is constant. Numerical experiments are given to show that two preconditioners based on circulant approximation, when applied to accelerate the CGNR and GMRES method, are efficient for solving the fractional diffusion equations.In Chapter 6, numerical solutions of fractional diffusion equation are further considered, the finite volume method(FVM) is used to discretize the steady-state Riesz space fractional diffusion equations, and the resulting systems possess Toeplitzlike structure. To reduce the amount of calculation in the preconditioner presented by Wang and Du(2013), two preconditioners based on Strang circulant approximation and -circulant approximation, and two preconditioners based on Strang skewcirculant approximation and -skew-circulant approximation are designed to accelerate the Krylov subspace methods for solving the Toeplitz structured linear systems.Theoretical analysis shows the proposed four preconditioners are all convergent. Numerical experiments are carried out to show that the effect of four preconditioner is obvious for accelerating conjugate gradient normal residual method(CGNR), conjugate gradient squared method(CGS) and Bi-conjugate gradient stabilized method(Bi CGstab). Meanwhile, for the tested three iterative methods and the steady-state Riesz space-fractional diffusion equations, there was no obvious difference in the accelerated effect of two preconditioners based on circulant approximation and two preconditioners based on skew-circulant approximation.Finally, a summary of the full thesis and future research directions are discussed in Chapter 7.