PDF Publication Title:
Text from PDF Page: 123
5.5.3 Preconditioning for non-stationary schemes Thus far we have examined the inner-outer algorithm as a stationary itera- tion. In this section we switch our viewpoint and examine it as a precondi- tioner for a non-stationary iteration. As such, we will be mainly interested in how well the eigenvalues of the preconditioned matrix are clustered. Consider an approximation of (I − βP ̄)−1 as a preconditioner for the PageRank linear system (I − αP ̄). Gleich et al. [2004] and Del Corso et al. [2007] examined the behavior of Krylov subspace methods on the system (I − αP ̄)y = (1 − α)v, (5.23) and concluded that, as expected in general, preconditioning is essential for the linear system formulation of the PageRank problem. Their preconditioners were incomplete factorizations or factorizations of diagonal blocks of the matrix, both of which modify the matrix data structure. System (5.23) is different from system (5.1) because we use P ̄ instead of P. It corresponds to using PseudoRank instead of PageRank, but the solutions We switch to the alternate formulation with P ̄ for two primary reasons: it converged more often in our experience (we have no insight into why this occurs); and the behavior of Krylov methods has been empirically studied more often on this formulation of the system. For β near α, the preconditioned system is as difficult to solve as the original linear system. We thus consider a Neumann series approximation, which is practically equivalent to a Richardson approach as in the basic inner- outer iteration: (I−βP ̄)−1 ≈I+βP ̄+(βP ̄)2 +⋯+(βP ̄)m. Since β < 1 and ∥P ̄∥1 ≤ 1, this approximation converges as m → ∞, and it gives rise to an implementation that only uses matrix-vector multiplies with P ̄ and avoids costly (or even impossible) modification of the matrix structure. Details on the performance of this approach are provided in section 5.6. of the two systems are proportional: x = y/∥y∥ .7 1 7 See section 2.2.1 for the definition and equivalence between PseudoRank and PageRank. Langville and Meyer [2006a, Theorem 7.2.1] also include a proof. The gist is that P = P ̄ +vdT and so ( I − α P ) x = ( I − α P ̄ ) x + γ v = ( 1 − α ) v . We can move γv to the right-hand side and compute y with an unknown scale. 5.5 ⋅ extensions 103PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |