Abstract
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 $\mathcal U$ of matrices, thereby obtaining an ER-$\mathcal U$ method, and we observe that ER-$\mathcal 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 $\mathcal U$ utilized requires a surplus of operations per step and memory allocations, which make ER-$\mathcal 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 $\mathcal U$, more efficient for huge graphs.
Please cite this work as:
@article{tudisco2011preconditioning,
title={A preconditioning approach to the {PageRank} computation problem},
author={Tudisco, Francesco and Di Fiore, Carmine},
journal={Linear Algebra and its Applications},
volume={435},
number={9},
pages={2222--2246},
year={2011},
publisher={Elsevier}
}