Fast Algorithm Research For Solving Large Sparse Structured Linear Systems

Large sparse structured linear(algebraic)systems arise from a wide variety of applications in computational science and engineering fields,such as the incompressible liquid flow problem,the widely used PDE constraint problems,the ill-conditioned inverse problems and so on.By using proper discretization,these problems can eventually be changed into large linear systems,which generally have some special structure,ill posed and singular properties.Numerical solution for solving linear systems is a central task in scientific and engineering computing,which is of great both theoretical and practical significance.In the face of the different structures of linear systems in practical problems,how to make use of the structure and characteristics of the problem itself to construct a stable and efficient algorithm 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 large sparse structured linear systems arising in the discrete PDE constrained optimization problems,a few kinds of PDE and ill-posed problems,focuses on a piece of 2×2 structure of linear system and propose a series of efficient and robust iteration methods and preconditioning techniques.In Chapter 1,we review the backgrounds and motivations of this thesis are introduced,and reviews the present research situation.The main contents,results and innovations of this thesis are given in the end of this chapter.In Chapter 2,we mainly study the numerical solution of the complex symmetric linear equations derived from several special partial differential equations(such as the Helmholtz equation).Two classes of block preconditioners with better properties are obtained to solve the the real equivalent block 2 × 2 linear system.Particularly,when(2- or -(2 is symmetric positive semidefinite,the exact eigenvalue bounds are obtained which are much tighter than the state of the art.At last,numerical experiments are presented to show the effectiveness of the optimized preconditioners.In Chapter 3,we mainly study the fast algorithm of the discrete structural linear system derived from the PDE constrained optimization problem.For a class of twoby-two complex linear systems arising from the optimal control problems constrained by time-harmonic parabolic equations,we further study and optimize the most effective three block preconditioners.The relationship between the three preconditioners is found and derived,i.e.,the eigenvalues of the corresponding preconditioned matrix are all affected by the same matrix.By discussing the selection of the optimal parameters,three most effective preconditioners are obtained.In addition,based on the idea of multi-step preconditioning,two two-step preconditioners are constructed.Theoretical analysis and numerical experiments have proved the effectiveness and robustness of these preconditioners.In chapter 4,we propose an effective iterative method for the structured linear system obtained from the image restoration problem.Based on new HSS(NHSS)preconditioner proposed by Pan et al.in 2014.By introducing two iterative parameters,a generalization of the NHSS preconditioner and the corresponding iterative method are presented.The convergence properties of the iterative method and the spectral properties of the preconditioned matrix are analyzed theoretically.The optimal choice of the parameters are discussed.Numerical experiments show that the GNHSS iterative method and the corresponding preconditioner have excellent performance when accelerating the GMRES method.In Chapter 5,we mainly focus on solving the saddle point structure linear system derived from the incompressible Navier-Stokes equations.An effective preconditioner is designed,the spectral properties of the preconditioning matrix are studied.The comparisons of complexity of the algorithms between the new preconditioner and the existing preconditioner are obtained,which shows that the new preconditioners enjoy the computational advantage.In addition,we also discuss the choice of optimal parameters and give a more practical selection for selecting parameter.Numerical examples are given to verify the validity and stability of the new preconditioners.In Chapter 6,a block product(BP)preconditioner is established to solve block two-by-two linear systems.Convergence analysis of the corresponding BP splitting iteration and spectral propensities of the BP preconditioned matrix are studied in depth.Besides,an explicit expression of quasi-optimal parameter is obtained and a practical estimate for the quasi-optimal parameters is given.Moreover,the implementation of the preconditioned method is given,which shows that the computational cost of applying the BP preconditioner to accelerate GMRES is lower as compared with some other preconditioners.The numerical results show that the BP preconditioner costs much less time at each step and is effect under the parameters we have provided.Finally,a summary of the full thesis and future research directions are discussed in the last chapter.