Krylov Subspace Algorithm For PageRank Problems And Random Kaczmarz Algorithm And Its Application

At present,many scientific computing and engineering applications often need to solve large sparse linear equations.Therefore,the problem of solving linear equations has always been an important field of research.The complexity of practical application problems often leads to the final linear equations will not only have a high dimension,but also have different matrix forms and properties.In this paper,we mainly study the PageRank problem of web page sorting and the numerical algorithm problem of solving large sparse linear equations by randomized Kaczmarz method,and the improved randomized Kaczmarz reconstruction algorithm is applied to the calculation of signal reconstruction in compressed sensing.The work we have done can be summarized as follows:1.In solving the PageRank problem,when the damping factor a is close to 1,the convergence rate of the existing numerical algorithms is often very poor.In view of this situation,the author has done two aspects of research work.First,in this paper,a precon-ditioned multi-step splitting iterative algorithm is presented by using the deeply restarted Arnoldi process and the multi-step splitting iterative method,and its convergence is an-alyzed and proved.At the same time,a related numerical example is given.Secondly,when the Arnoldi process is used to calculate the PageRank problem,it is found that when the damping factor a is sufficiently close to 1,the convergent residual curve will jump irregularly or even not converge.Based on the analysis of the reasons,the author puts forward the GMRES-Power method.The numerical experiments verify the results of the theoretical analysis and show the numerical effectiveness of the algorithm.2.The randomized Kaczmarz algorithm proposed in 2009 and the greedy random-ized Kaczmarz algorithm proposed in 2018 are two effective methods for solving large coefficient linear equations.Based on these two algorithms,two improved algorithms are given.The first improved algorithm:based on the greedy randomized Kaczmarz method,by making full use of the residual information calculated by the greedy random-ized Kaczmarz algorithm in each iteration,In this paper,a multi-step greedy randomized Kaczmarz method is proposed,and the convergence of the algorithm is proved.Numeri-cal examples are given to verify the effectiveness of the algorithm.The second improved algorithm:based on the relaxed randomized Kaczmarz algorithm,an adaptive multi-step relaxed randomized Kaczmarz method is presented,and the convergence of the algo-rithm is proved.several numerical examples are given to verify the effectiveness of the algorithm.3.Based on the randomized sparse Kaczmarz method,an adaptive multi-step greedy randomized sparse Kaczmarz method is proposed by using the adaptive multi-step relaxed randomized Kaczmarz method.And it is applied to the solution of signal reconstruction of compressed sensing problem.The specific image numerical experi-ments show that the adaptive multi-step greedy randomized sparse Kaczmarz method is much faster than the randomized sparse Kaczmarz method in convergence speed,and CPU time spent on computing is also much less than the randomized sparse Kaczmarz method.