Title
A Note on the Convergence of SOR for the PageRank Problem
Abstract
A curious phenomenon when it comes to solving the linear system formulation of the PageRank problem is that while the convergence rate of Gauss-Seidel shows an improvement over Jacobi by a factor of approximately two, successive overrelaxation (SOR) does not seem to offer a meaningful improvement over Gauss-Seidel. This has been observed experimentally and noted in the literature, but to the best of our knowledge there has been no analytical explanation for this thus far. This convergence behavior is surprising because there are classes of matrices for which Gauss-Seidel is faster than Jacobi by a similar factor of two, and SOR accelerates convergence by an order of magnitude compared to Gauss-Seidel. In this short paper we prove analytically that the PageRank model has the unique feature that there exist PageRank linear systems for which SOR does not converge outside a very narrow interval depending on the damping factor, and that in such situations Gauss-Seidel may be the best choice among the relaxation parameters. Conversely, we show that within that narrow interval, there exists no PageRank problem for which SOR does not converge. Our result may give an analytical justification for the popularity of Gauss-Seidel as a solver for the linear system formulation of PageRank.
Year
DOI
Venue
2011
10.1137/110823523
SIAM J. Scientific Computing
Keywords
Field
DocType
similar factor,pagerank model,linear system,narrow interval,situations gauss-seidel,linear system formulation,convergence behavior,convergence rate,analytical explanation,pagerank problem,linear systems,gauss seidel
Convergence (routing),PageRank,Mathematical optimization,Existential quantification,Linear system,Matrix (mathematics),Rate of convergence,Solver,Mathematics,Gauss–Seidel method
Journal
Volume
Issue
ISSN
33
6
1064-8275
Citations 
PageRank 
References 
3
0.50
0
Authors
2
Name
Order
Citations
PageRank
CHEN GREIF132143.63
David Kurokawa2997.15