PDF Publication Title:
Text from PDF Page: 136
114 5 ⋅ an inner-outer iteration for pagerank 5.5.2 Inner-Outer Gauss-Seidel iterations The performance of Gauss-Seidel applied to the PageRank linear system (I − αP)x = (1 − α)v is considered excellent, given its modest memory requirements. It often converges in roughly half the number of power method iterations. However, from a practical point of view, two pitfalls of the method are that it requires the matrix P by rows (i.e. the graph by in-edges) and it does not parallelize well. We can accelerate Gauss-Seidel using inner-outer iterations, as follows. Our Gauss-Seidel codes implement the dangling correction to the matrix P ̄ implicitly and match those in the law toolkit [Vigna et al., 2008]. To convert the inner-outer method to use Gauss-Seidel, we replace the inner Richardson iteration (5.6) with a Gauss-Seidel iteration. In our pseudo- code, presented in algorithm 4, the gssweep(x, A, b) function implements x(k+1) = M−1 (N x(k) + b) in-place for a Gauss-Seidel splitting of the ma- GS GS trix A.6 The gauss-seidel-pr function in line 7 of the algorithm refers to the standard “Gauss-Seidel for PageRank” scheme described in section 2.4.3 starting with the current x. This algorithm only requires two vectors of stor- age because x is always updated in-place. Details on the performance of this algorithm are provided in section 5.6. Algorithm 4 – The inner-outer/Gauss-Seidel iteration. Input: P, α, β, τ, η, v Output: x 1: x ← v 2: y ← Px 3:while ∥αy+(1−α)v−x∥1 ≥τ 4: f ←(α−β)y+(1−α)v 5: for i = 1, 2, . . . 6: x,δ←gssweep(x,I−βP,f){δ=∥x(i+1)−x(i)∥ } 1 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. 6 This function is explicitly de- scribed in section 2.4.3. 7: until δ < η 8: if i=1, gauss-seidel-pr(x, I − αP, (1 − α)v); break 9: y ← Px 10: end repeat 5.5.3 Preconditioning for non-stationary schemesPDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.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 |