PDF Publication Title:
Text from PDF Page: 150
128 5 ⋅ an inner-outer iteration for pagerank This generalizes the results of the previous experiment. The ratios in the table are the change in iterates, not the error in the solution. This makes techniques based on these numbers amenable to computations. The table suggests a strategy to apply the inner-outer iterations dynamically. For the two smallest graphs we have computed all the eigenvalues, and observe the expected convergence based on λ until the round-off error inherent in the power iteration restores the component of error in the eigenmodes on the unit circle. We could build an algorithm to watch for an increase in the ratio, or watch for when the ratio gets sufficiently close to α, and then apply additional inner-outer iteration pairs to reduce the magnitude of these eigenvalues. These experiments motivate the following conjecture. Conjecture18. Theasymptoticconvergencerateoftheinner-outeriterationis αλ2, where λ2 is the eigenvalue inside the unit circle with largest magnitude. We offer the following support for the conjecture. Consider an eigenvalue of P on the unit circle: λ = e i θ . If the outer iterations are solved exactly, then (α−β)λ we reduce the error in the associated eigenvector by 1−βλ . With β = 0.5, all eigenvalues different from one achieve some reduction and the largest reduction is for eigenvectors with eigenvalue −1. For the power method, none of these eigenvalues is reduced by more than α. Thus, the inner-outer method does reduce the error associated with eigenvalues on the unit circle. summary The inner-outer iteration solves a PageRank problem via a series of Page- Rank problems with smaller values of α. Outer PageRank problems are solved via an inner Richardson iteration. The subsequent algorithm always con- verges for PageRank (theorem 17). In addition, we combine the inner-outer idea with the power method (section 5.5.1), the Gauss-Seidel method (sec- tion 5.5.2), and the BiCG-STAB method (section 5.5.3). All of these ideas reduce the number of matrix-vector products (or an equivalent work metric) required to converge to a PageRank vector for α > 0.85. We also analyze OpenMP shared memory parallelism and provide a conjecture about why the inner-outer iteration is faster (conjecture 18). As a final note, the inner-outer algorithm is low-memory, easy to im- plement, and robust—it has become our PageRank solver of choice when Gauss-Seidel iterations are not practical.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 (Standard Web Page)