PDF Publication Title:
Text from PDF Page: 142
120 5 ⋅ an inner-outer iteration for pagerank 5.6.2 Inner-Outer Gauss-Seidel We present our comparison for the Gauss-Seidel method in table 5.3. Rather than matrix-vector multiplications, the results are measured in sweeps through the matrix. The work for a single sweep is roughly equivalent to a single matrix-vector multiplication. For α = 0.99, the inner-outer iteration only accelerates two of our smallest test graphs. Increasing α to 0.999 and using a strict τ shows that the inner-outer method also accelerates Gauss- Seidel-based codes. We have not invested effort in optimizing the scheme in this case; our experiments are only intended to show that the inner-outer idea is promising in combination with other high-performance PageRank techniques. We believe that an analysis of the sort that we have performed for the Richardson iteration in the previous sections may point out a choice of parameters that could further improve convergence properties for the inner-outer scheme combined with Gauss-Seidel. Table 5.3 – Performance of the Gauss-Seidel inner-outer iteration. Total number of Gauss-Seidel sweep iterations (equivalent in work to one matrix-vector multiply) and wall-clock time required for convergence, and the corresponding relative gains defined by (5.24). The param- eters used here are β = 0.5 and η = 10−2 and we used Matlab mex codes. The convergence tolerance was τ = 10−7 . α graph work gs in/out gain gs (secs.) in/out gain 2.7 7.0% 18.0 7.7% 67.3 -2.2% 60.4 -6.6% 380.0 -6.2% 16.8 14.9% 113.8 19.7% 391.0 13.3% 352.4 0.7% 2249.0 11.2% 0.99 ubc-cs-2006 ubc 566 503 11.1% in-2004 473 469 0.8% eu-2005 439 462 -5.2% wb-edu 450 464 -3.1% 2.9 19.5 65.9 56.6 357.9 19.8 141.6 451.1 354.8 2532.5 (sweeps.) time 562 492 12.5% 0.999 ubc-cs-2006 ubc 4597 in-2004 3668 eu-2005 3197 wb-edu 3571 5.6.3 Parallel speedup 4430 3576 19.3% 3646 20.7% 3147 14.2% 3159 1.2% 3139 12.1% Parallel PageRank algorithms take many forms [Gleich et al., 2004; Kollias et al., 2006; McSherry, 2005; Parreira et al., 2006]. Our implementation sub- stitutes OpenMP shared memory operations for the linear algebra operations norm, axpy, and the matrix-vector multiply. We implemented two versionsPDF 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 |