Multigrid Algorithms For Markov Chains And Numerical Solutions Of Pagerank Problems

This dissertation focuses on numerical methods for solving the linear systems which arise from Markov chain problems and PageRank problems.We study the type of adaptive aggregation multigrid methods,and then propose several techniques to accelerate these methods for solving Markov chain problems.Besides,we study the special structures and properties of PageRank problems,and then propose several numerical methods to accelerate solving processes of this type of problems.The research contents and achievements can be briefly introduced as follows:1.We study the adaptive aggregation multigrid method and its smoothed version.The multigrid hierarchies of this type of methods are constructed based on aggregation processes that classify nodes into aggregates.Thus,the aggregation algorithms are important for the efficiency of this type of methods.However,the widely used NeighbourhoodBased aggregation algorithm sometimes generates inapposite aggregates,decreasing the efficiency of adaptive aggregation multigrid methods.We deeply analyze the design of this aggregation method,and propose a refined version.Numerical experiments demonstrate that,the refined Neighbourhood-Based aggregation method can generate appropriate aggregates more stably than the original version and thus can improve the efficiency of adaptive aggregation multigrid methods when solving Markov chains.2.The type of adaptive aggregation multigrid methods update aggregates at every iterative step.Although such strategy guarantees the efficiency of coarse-level corrections and accelerates iterative processes,it also increases the cost per iteration remarkably.We analyze the mechanism of generating aggregates in these methods and propose a strategy to update aggregates dynamically.Theoretical analyses and numerical experiments demonstrate that,this strategy can reduce dramatically the times of updating aggregates without affecting the convergence rate of adaptive aggregation multigrid methods,and thus it can reduce remarkably the time needed by this type of methods for solving Markov chains.3.We study the characteristic of the aggregates generated in adaptive aggregation multigrid methods and demonstrate that: the aggregates on each level of such methods can be used to transfer the probability equation of that level into a block linear system that is nearly block diagonally dominant.Based on this observation and some theories of Schwarz methods,we propose a block relaxation algorithm to replace the point-wise relaxation algorithm in adaptive aggregation multigrid methods for improving the efficiencies of relaxation processes.We have proved the implementability and the convergence of this block relaxation at each level of these multigrid methods when solving Markov chains.Besides,PageRank problems can also be stated as solving Markov chain linear systems,but in this case the coefficient matrices are usually fully dense.We propose some computational techniques for the proposed block relaxation to avoid operating dense matrices when solving PageRank problems.Numerical experiments have illustrated the effectiveness of the proposed block relaxation for accelerating solving processes of Markov chain problems and PageRank problems.4.We study the structural characteristics of Web link graphs and the numerical properties of the transition matrix of the PageRank problem.Then we propose an elimination algorithm that compares the patterns of the rows in the transition matrix to decrease the density of the linear system of the PageRank problem.We also analyze the effect of this elimination algorithm on changing the spectral distribution of the PageRank linear system.Numerical experiments demonstrate that,this elimination algorithm can transfer the PageRank linear system into another linear system that is easier to be solved.5.Following the aforementioned study on the transition matrix of the PageRank problem,we derive a special property of the coefficient matrix of this problem.Based on this property,we propose a low-rank factorization scheme and a matrix partition algorithm to transfer the coefficient matrix into a block matrix and compress its off-diagonal part.As a result,we get a low-rank expression of this block matrix.Then we propose a preconditioner based on the low-rank expression.We have proved the implementability of this preconditioner and analysed its efficiency on accelerating the iterative process.Numerical experiments have demonstrated the effectiveness of the proposed techniques for accelerating the solving processes of PageRank problems.