PDF Publication Title:
Text from PDF Page: 050
28 2 ⋅ pagerank background on a graph Further optimizations of the power method are possible on standard graph data structures in other languages. First, constructing the sub-stochastic matrix explicitly is not required on most graph structures. Implicitly using the degree normalization saves memory. Second, in pro- gram 2, the quantity delta is computed after y is completely updated. In- stead, the program could accumulate this quantity while updating the vector y. Section 6.5.2 provides an optimized iteration on a compressed web graph structure. 2.4.3 Gauss-Seidel For the PageRank linear system (I − αP)v = (1 − α)v, an extremely simple linear solver is the Jacobi method. It is nearly the same as the Richardson iteration, but a few subtle differences confuse the two. (Looking at these differences is a fun exercise that won’t be covered here.) A close cousin of the Jacobi method is the Gauss-Seidel iteration, which is asymptotically faster [Varga, 1962]. See [Arasu et al., 2002; Del Corso et al., 2005] for comprehen- sive evaluations of the performance of Gauss-Seidel. It is fast and often takes only half the iterations of the power method with exactly the same work per iteration (or nearly so). The easiest way to understand the Gauss-Seidel iteration is to imagine a particular programming error in the Jacobi iteration. Thus there is no avoiding the Jacobi iteration, and we begin by describing it. For Ax = b, split A = DA − NA into its diagonal and negated off-diagonal components and then iterate: x(k+1) = DA−1(b + NAx(k)). If A is stored by rows, then a simple implementation is ⎛n⎞ (k+1) (k) xi = bi −∑Aijxj /Aii i=1,...,n. ⎝⎠ j =/ i Under well studied conditions, this iteration converges. Implementing this iteration requires allocating both x(k) and x(k+1). Gauss-Seidel follows by “forgetting” to allocate x(k+1) and updating x(k) in place, that is ⎛n⎞ (k) (k) xi ← bi −∑Aijxj /Aii i=1,...,n. (2.22) ⎝⎠ This change is reasonable and corresponds to using the most recent values of all the variables while solving the equations. j =/ iPDF 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 |