Monday,
March 27, 2006, 3:40 p.m. PSA 113
Dept. Comp. Sci., Stanford University
Numerical Methods for Rapid Computation of Page Rank
Abstract
We consider the problem of iteratively computing the stationary
distribution vector of large finite Markov chains. It is assumed that the
matrices involved are too large for a decompositional approach to be
effective, and matrix-vector products must be used. The problem is
motivated by Google's PageRank algorithm for large web databases. We
consider an Arnoldi-type restarted algorithm based on a combination of
Arnoldi and the SVD. Connection of the algorithm to other techniques such
as the quadratic extrapolation method is discussed, and the sensitivity of
the PageRank problem is also addressed. Numerical examples illustrate the
performance and convergence behavior of the algorithm.
This work is joint with Chen Grief.
For further information please contact:
Anne Gelb