ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

Contributed talks on Graphs and Networks

Thu 14:30–15:00, Room AV 01.12, Chair: Francisco Pedroche
An efficient preconditioner exploiting the sparsity and row similarity for PageRank problems
Zhaoli Shen (University of Groningen)
Joint work with Tingzhu Huang (University of Electronic Science and Technology of China); Bruno Carpentieri (Nottingham Trent University UK); Chun Wen (University of Electronic Science and Technology of China)

The PageRank problem can be mathematically stated as the following system $(I-\alpha P)x=v$, where $0<\alpha<1$, $P$ is a transition probability matrix constructed from the web structure, $v$ is a positive vector and $x$ is the unknown PageRank vector. Due to the huge size of this system, iterative methods are mandatory to use for solving it. However, when $\alpha$ approaches 1, i.e., the model reflects more closely the web structure, iterative solvers tend to suffer slow convergence caused by the unfavourable spectral distribution and the high condition number of the matrix $I-\alpha P$. Thus preconditioning is necessary.

In this study we exploit the sparsity of the web structure to permute the PageRank matrix $(I-\alpha P)$ into a 2 by 2 block form $[B,F;E,C]$, where $B$ is an easy to invert large lower triangle matrix. This permutation reduces the preconditioning cost of the PageRank problem to inverting a small Schur complement matrix $S=C-EB^{-1}F$. Meanwhile we propose a partial low-rank factorization which efficiently compresses similar rows in $E$, $F$, and $C$. Accordingly the PageRank matrix is formulated as $[B,\tilde{F};\tilde{E},\tilde{C}]+UV$, where $\tilde{E}$, $\tilde{F}$ and $\tilde{C}$ are much more sparse than $E$, $F$ and $C$, respectively, and consequently the new Schur complement $\tilde{S}=\tilde{C}-\tilde{E}B^{-1}\tilde F$ is more sparse than $S$, while $U$ and $V$ are two low-rank rectangular matrices. Upon this pre-processing step, we propose a preconditioner formulation based on the Woodbury formula. We demonstrate some theoretical properties of this preconditioner and we report on numerical experiments to support our theoretical findings.