Lumping Method with Acceleration for the PageRank Computation

Web information retrieval is extremely challenging due to the huge number of web pages. The success of a search engine relies on its capacity to deploy fast, accurately and in order, a set of results satisfying a particular query. To determine the order of importance in which to display web pages after a query, Google´s search engine computes the Page Rank vector, the left principal eigenvector of a web matrix that is related to the hyperlink structure of the web, the Google matrix. From a computational mathematics viewpoint the most important part of the Google search engine is the Page Rank computation, mainly the numerical linear algebra behind as well as the use of adequate techniques to accelerate its computation. In this work we intend to contribute for the acceleration of the Page Rank computation by combining reordered techniques with extrapolation. We propose a novel algorithm by considering standard extrapolation within the lumping method. Results show the benefits from our proposal.