PDF Publication Title:
Text from PDF Page: 146
124 5 ⋅ an inner-outer iteration for pagerank Gleich et al. [2004] and [Del Corso et al., 2007] explored the performance of preconditioned BiCG-STAB on the PageRank system. We have modified the Matlab implementation of BiCG-STAB to use the 1-norm of the residual as the stopping criterion. To compare against the power-method and Gauss-Seidel, the normalized solution vectors x = y/∥y∥1 always satisfy ∥αPx(k) + (1 − α)v − x(k)∥ ≤ τ. This criterion is equivalent to taking one step of the power method and check- ing the difference in iterations. Consequently, all the solution vectors tested are at least as accurate as the vectors computed in the power method with tolerance τ. In practice, we did not test the previous solution criterion at every iteration and instead modified the Matlab BiCG-STAB function to terminate the computation when the 1-norm of the residual was less than √√ ( 1 − α)τ. Empirically, using ( 1 − α)τ as the tolerance for BiCG-STAB yielded y’s that satisfied our actual tolerance criterion without a full rewrite of the residual computations. BiCG-STAB diverges or breaks down on in-2004 without precondition- ing for α = 0.99, see table 5.4. This matches observations by Del Corso et al. [2007] that Krylov methods often have convergence difficulties. Adding the preconditioner with m = 2 and β ≥ 0.5 avoids these break-down cases. The remainder of the table shows that preconditioning accelerates conver- gence in many cases for “reasonable” parameter choices. Among the methods discussed, BiCG-STAB with this preconditioner converges with the fewest matrix-vector multiplications on the in-2004 graph with α = 0.99 and α = 0.999. However, the cost per iteration is higher. 5.6.5 Other applications The IsoRank algorithm [Singh et al., 2007] is a heuristic to solve the net- work alignment problem. Given two graphs, A and B, the goal in the network alignment problem is to find a match for each vertex of graph A in B and vice-versa. The resulting matching should maximize the number of cases whereiinAismappedto jinB,i′ inAismappedto j′ inB,andbothof the edges (i, i′) ∈ A and (j, j′) ∈ B exist. This objective alone is NP-hard. Often there are weights for possible matches, e.g. Vji for i in A and j in B, that should bias the results towards these matchings, and hence the objective also includes a term to maximize these weights.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 |