Efficient Row And Column Iterative Methods And Anderson Acceleration Methods With Damping Optimization For Large-scale Linear Equations

In scientific and engineering computing fields such as artificial intelligence,big data analysis and mining,the efficient solution of large-scale linear equations is still one of the core problems in high precision numerical simulation,high performance numerical algorithm and software development.In this dissertation,by using the theoretical knowledge and methods of numerical algebra,stochastic optimization,probability statistics and so on,we propose some efficient row and column iterative methods as well as the AA method with novel damping optimization for large-scale linear equations.The main works and conclusions are as follows:In order to accelerate the convergence rate of the fast deterministic block Kaczmarz(FDBK)method for large-scale consistent linear equations,firstly,based on the approximate maximum residual sampling criterion,we present a fast deterministic pseudoinverse-free block extension of Motzkin(FBEM)method and establish its convergence theory.Secondly,by incorporating the heavy-ball momentum acceleration technique into the FBEM method,we establish the accelerated FBEM(m FBEM)method and obtain its global linear convergence.Finally,numerical experimental results show that the FBEM method and the m FBEM method are effective in solving large-scale consistent linear equations,and further confirm that the heavy-ball momentum method is an effective acceleration technique.In order to solve the large scale factorised linear equations efficiently,firstly,by using the randomized Gauss-Seidel(RGS)method to replace the randomized extended Kaczmarz(REK)method for solving the subsystems,we develop the RGS-RK method which can make full use of the factorised structure of the coefficient matrix,and then give its convergence theory.Secondly,by introducing the relevant theories and methods of block scheme and pseudoinverse-free block iteration method into the RK-RK method and the REK-RK method,we propose the randomized average block RK-RK(BRK-RK)method and the randomized average block REK-RK(BREK-RK)method to solve large-scale factorised linear equations.The new methods can still make full use of the factorised structure of the coefficient matrix,and can be used for parallel computation without computing pseudoinverse or solving the least squares problems.Then,we establish the convergence theories of the BRK-RK method and the BREKRK method based on the randomized iteration theories and methods.Finally,numerical results demonstrate that the RGS-RK method,the BRK-RK method,and the BREKRK method can achieve significant acceleration effects,which further confirm that the pseudoinverse-free block scheme is an effective way to improve the computational efficiency of randomized iterative methods for solving large-scale factorised linear equations.In order to further improve the numerical results of the Anderson Accelerated(AA)method for solving large-scale linear equations,by introducing local optimization strategies and preconditioning techniques into the AA method,a new optimal damping factor is developed and a specific computation formula is given.Then,a preconditioned AA(PAAopt(m))method with new optimized damping is proposed.Secondly,the convergence theory of the PAAopt(m)method for solving linear fixed point problems is given,and the one-step iterative numerical characteristics of the PAAopt(m)method is studied,and then the relevant convergence theory is established.Finally,the numerical results show that PAAopt(m)has a significant acceleration effect,and further confirm that the optimization of damping factors is an important way to improve the numerical solution effect of the AA method.