A Research Of Biconjugate A-Orthonormalization Based Krylov Subspace Methods And A Lanczos Based Preconditioner

The contents presented in this thesis involve four compositions: the first part is areview of the previous works about the Biconjugate A-Orthonormalization procedure, in-cluding the deducing process of the method and relevant algorithms based on this method;the second part is to propose two new Krylov subspace methods that are based on the Bi-conjugate A-Orthonormalization procedure; the third part shows a series of numericalexperiments aiming to testing the two new methods, in which one class of numerical ex-amples in the experiments is derived from signal deconvolution problems and the otherclass of numerical examples is nonsymmetric linear system with complex spectrum.In the last century, several excellent scholars have proposed a series of numericalmethods that were able to solve large-scale linear systems effectively, such as CG, CRand MINRES for symmetric linear systems, and GMRES, BiCG and its variants for non-symmetric linear systems. In2009, Yan-Fei Jing, etc. proposed a new type of methodsnamed the Lanczos Biconjugate A-Orthonormalization based Krylov subspace methods,such as BiCOR, CORS and BiCORSTAB. In numerical experiments, these new meth-ods perform better convergence with a smoother iterative curve and faster convergencespeed. Both CORS and BiCORSTAB share a similar idea to decrease the computation-al cost that they take advantage of polynomials to avoid the extra calculation from thematrix transposition-vector product. Comparing with the original BiCOR, we can classi-fy CORS and BiCORSTAB in a same category. In the thesis, we propose a generalizedpolynomial-type framework method of BiCOR, in which CORS and BiCORSTAB canbe regarded as two particular variants under this framework with different parameters de-rived from various ideas. Furthermore, the generalized polynomial-type BiCOR method,GPBiCOR hereinafter for short, gives us a result in numerical experiments, which is su-perior, or not inferior at least, to CORS and BiCORSTAB on the computational time andthe rate of convergence. A class of numerical examples are from the signal deconvolutionproblem. In these numerical experiments, GPBiCOR shows us a delighting result. Underthis framework, we expect to discover more effective methods of high efficiency in thenew field of Biconjugate A-Orthonormalization based theories.Moreover, the rate of convergence will be impaired heavily when the spectrum of the coefficient matrix is complex, which can be considered to be caused by the complexroots of the introduced polynomials, like the ones in BiCORSTAB. In order to lower oreliminate the negative effect, we introduce different recursive formulas of polynomialsto reach the optimal goal in particular cases. In this thesis, two different kinds of poly-nomials are executed alternatively one by one for the purpose of the elimination of theweakness caused by the complex spectrum of the coefficient matrix. In concrete imple-mentation, we partially remain the recursive formula of BiCORSTAB and make use of anew recursive formula that is based on the information of the previous two iterative stepsin the rest in order to have a better numerical result in the cases with complex spectrum.In corresponding experiments, we can obviously observe that the new proposed methodperforms better than BiCOR and its classic variants CORS and BiCORSTAB.In sum, we can classify all variants of the original BiCOR, which are optimized bythe utilization of polynomials, as a generalized method called GPBiCOR proposed in thisthesis. We first give a framework of polynomial-type BiCOR for the purpose that readersare able to have a simple, direct, and global realization of the class of methods. Underthis framework, we can explore other methods benefiting from the advantage of the Bi-conjugate A-Orthonormalization procedure to handle particular problems. The methodfor solving nonsymmetric linear system with complex spectrum provides us an effectivesolver for the problems arising from the discretization of both partial differential and inte-gral operators in many application fields. It has high scientific relevance and applicability,and thus it is a welcome addition to the subject of Krylov subspace methods in numericallinear algebra.Furthermore, we propose a Lanczos based preconditioner for least squares problemsin overdetermined and underdetermined cases. Generally, we translate the least squaresproblems into normal equations and then make use of the methods for solving ordinarylinear systems to make it. The singular values of least squares problems will be reflect-ed in the eigenvalues of the corresponding normal equations so that the largest singularvalue will cause a large eigenvalue of normal equations that impairs the convergence ratebecause of a bad spectrum. The preconditioner is designed to minish the largest singularvalue in order to contract the spectrum for a better convergence. Also, we present relevant numerical experiments to illustrate the effect of the Lanczos based preconditioner that isproposed in this thesis.