PDF Publication Title:
Text from PDF Page: 144
122 5 ⋅ an inner-outer iteration for pagerank on p processors compared with the best time on 1 processor. The higher rela- tive speedup of methods based on the in-edges of the graph (6-7x) compared to out-edge methods (5-6x) demonstrates that in-edge algorithms are more scalable. In light of the atomic operation in out-edge methods, this paral- lelization difference is not surprising. No consistent differences appear when comparing the relative speedup of the inner-outer method and the power method. Consequently, we assume that these methods parallelize similarly and compare true speedup. For an out-edge graph, the true speedup and relative speedup are similar. In contrast, the relative speedup for an in-edge graph is much higher than the true speedup. Gauss-Seidel causes this effect, since it is the fastest method on an in-edge graph and so the true speedup of most methods starts at around 0.5, a 50% slowdown. With one exception, the inner-outer methods (dashed lines) all demonstrate a higher true speedup than the power method. 5.6.4 Preconditioning We evaluate (I−βP ̄)−1 or its Neumann series approximation as a precondi- tioner, see section 5.5.3, by examining eigenvalue clustering and matrix-vector multiplies. To understand the preconditioner’s effect on the convergence of Krylov subspace methods, we look at clustering of eigenvalues of the matrix (I − βP ̄)−1(I−αP ̄).Letλi, i=1,...,nbetheeigenvaluesofP ̄.Ifwesolvethe preconditioned iteration defined by (I − βP ̄)−1 exactly, then the eigenval- ues of the matrix P ̄ undergo a Möbius transform to the eigenvalues of the preconditioned system, tion of the eigenvalues is no longer a Möbius transform, but the polynomial pm(λ) = (1 − αλ)(1 + βλ + ⋯ + (βλ)m). (5.26) Of course as m → ∞, we recover the exact preconditioned system. To illustrate the spectral properties of the preconditioned system, figure 5.4 shows the behavior of the preconditioned eigenvalues of two test matrices, for a variety of choices of β and m. In these examples, our preconditioner concentrates the eigenvalues around λ = 1. Solving the system exactly appears unnecessary as we see a strong concentration with even m = 2 or m = 4 terms of the Neumann series, for the values of β we tested. 1 − αλ 1 − βλ . (5.25) p(λ) = When we precondition with only a finite number of terms, then the modifica-PDF 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 |