Mathematical Analysis of Large Data Sets

Monday, March 27, 2006, 3:40 p.m. PSA 113

Gene Golub

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