Title: An Inner-Outer Iteration for Computing PageRank

Speaker: Chen Greif, The University of British Columbia

Abstract:
We present a new iterative scheme for computating stationary distribution 
vectors in Markov chains of the sort that arises in the PageRank model. 
The algorithm is applied to the linear system formulation of the problem, 
using inner-outer stationary iterations. It is simple, can be easily 
implemented and parallelized, and requires minimal storage overhead. The 
same approach can also be used as a preconditioning technique for 
non-stationary schemes. Our convergence analysis shows that the algorithm 
is effective for a crude inner tolerance, and the convergence rate seems 
to be minimally sensitive to the presence of eigenvalues of the 
non-parameterized PageRank matrix on the unit circle. Numerical examples 
featuring matrices of up to dimensions exceeding 100 million in sequential 
and parallel environments confirm the analytical results and demonstrate 
the merits of the proposed technique.