A preconditioning approach to the pagerank computation problem

Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ER_U method, and we observe that ER_U can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ER_U superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.