Numerical Algorithms For Markov Chains And Web Ranking

This dissertation deeply studies the iterative methods, accelerating methods and preconditioning techniques for solving the common linear algebraic systems and those from discrete time Markov chain problems, and then these methods are used for Web ranking problems.A generalized minimal residual method for large scale linear algebraic systems is studied and therein the initial iterative values in each cycle are improved by the vector extrapolation method to speed up accordingly. And then these ideas are applied to solve Markov chain problems. Numerical experiments show the progress in robustness of GMRES method by the proposed new algorithms and the remarkable effects have been achieved after the implementations of the new algorithms in terms of iteration numbers and CPU time.The algebraic multigrid method is applied to solving Markov chain problem. Given that the time required for getting interpolation operator, restriction operator and iterative matrix is undeniable, the extrapolation-acceleration strategy is introduced to improve the initial iterative values of each cycle on the finest level of AMG. Numerical results show the desired effects. At the same time, the new method is applied to the Web ranking problems and the accordingly experimental results illustrate that the proposed method has better performance than the traditional Web ranking methods.The linear system mode is studied to solve the Web ranking problems. Particularly in the case that the damping factor is close to 1 and the restarted GMRES method diverges or stagnates, the polynomial right-preconditioning strategy is adopted and the corresponding algorithm is then presented. And the convergence theorems of the new algorithm are then presented and proved. Furthermore, the re-acceleration on the basis of precondition is conducted and the hybrid PageRank algorithm follows. In the experimental research part, we first confirm the improvement of eigenvalue distribution of coefficient matrix.And then we verify that the proposed algorithms have improved the convergence and speed of the classical PageRank algorithm, from both iteration numbers and CPU time,perspectively.One of the regrets in classical PageRank algorithm is its evenly-distribution of one page’s authority value to all its outlinked pages. And thus would result in a drop in Web ranking quality and advents of business speculation or spamming. By introducing different weights three improved strategies are adopted to resolve this problem and the accordingly weighted algorithms based on linkage are given. Finally, experiments illustrate the validity of the new algorithms.The preconditioned Gauss-Seidel methods by alternate iteration and new preconditioners are introduced to resolve the linear algebraic system. Theoretical and empirical studies are real validation of the new preconditioning techniques.