PDF Publication Title:
Text from PDF Page: 128
106 5 ⋅ an inner-outer iteration for pagerank yielding the inner iteration, y(0)≡x(k); y(j+1)=βPy(j)+f(k) j=1,...,l; x(k+1)≡y(l). (5.6) We discuss how to terminate this iteration below, and show that keeping l small will accelerate convergence. The above scheme was initially proposed by Gray et al. [2007] in a tech- nical report. Subsequently, we have developed a new convergence analysis showing that the iteration always converges, a large-scale multi-core parallel implementation, a Gauss-Seidel variant, and an “inner-outer” preconditioner for PageRank with the BiCG-STAB solver [van der Vorst, 1992]. These addi- tions are reported in Gleich et al. [to appear]. The goal of our inner-outer idea is a low-memory, matrix-free,3 and para- meter-free scheme to compute PageRank faster than the power method. Al- though we introduce the parameter β in the definition of the method, we show analytically and experimentally that β = 0.5 is an effective choice. The result is a PageRank scheme that takes merely three vectors of memory and consistently outperforms the power method by a substantial margin in time and matrix-vector products (see table 5.2, figure 1.4). Because the method is matrix-free, it is easy to parallelize, provided a parallel matrix-vector product exists. We present experiments demonstrating the parallel performance of the inner-outer algorithm on matrices with over 100,000,000 rows and 3.7 bil- lion non-zeros. Similar ideas give both an inner-outer Gauss-Seidel method and a matrix-free preconditioner for the BiCG-STAB iteration. These contri- butions are discussed below, as well as a non-web application of PageRank with the IsoRank algorithm [Singh et al., 2007]. 5.1 existing pagerank algorithms Improving the computation of PageRank is not a new problem, though we are not aware of any other PageRank specific method that simultane- ously satisfies all three criteria of our inner-outer algorithm: low-memory, matrix-free, and parameter-free. Our algorithm converges much faster than the power method, which is the only previous algorithm that has these three properties. We briefly summarize the existing literature. When looking at the linear system from (5.1), Arasu et al. [2002] investigated the Gauss-Seidel method, which is not matrix-free. Later, McSherry [2005] suggested a modi- fication of the Richardson iteration that exploits matrix structure. Some of the first improvements on the eigenvector problem were acceleration and 3 A matrix-free method relies only on the availability of a matrix- vector product, and not the matrix itself.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 |