# A preconditioning approach to the Pagerank computation

Francesco Tudisco,
Carmine Di Fiore,

**Linear Algebra and its Applications**,
435 :
2222--2246
(2011)

### 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}
}
```

**Links:**
doi

Keywords:
Pagerank
Iterative methods
Preconditioning
Eigenvalues
Fast discrete transforms
matrix algebras