document: Extrapolation methods for accelerating PageRank computations We present a novel algorithm for the fast computation of PageRank , a hyperlink-based estimate of the '' importance '' of Web pages . The original PageRank algorithm uses the Power Method to compute successive iterates that converge to the principal eigenvector of the Markov matrix representing the Web link graph . The algorithm presented here , called Quadratic Extrapolation , accelerates the convergence of the Power Method by periodically subtracting off estimates of the nonprincipal eigenvectors from the current iterate of the Power Method . In Quadratic Extrapolation , we take advantage of the fact that the first eigenvalue of a Markov matrix is known to be 1 to compute the nonprincipal eigenvectors using successive iterates of the Power Method . Empirically , we show that using Quadratic Extrapolation speeds up PageRank computation by 25-300 % on a Web graph of 80 million nodes , with minimal overhead . Our contribution is useful to the PageRank community and the numerical linear algebra community in general , as it is a fast method for determining the dominant eigenvector of a matrix that is too large for standard fast methods to be practical .
doc_bio_tags: O O O O B O O O O O O O O O O O B O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O