PDF Publication Title:
Text from PDF Page: 130
110 5 ⋅ an inner-outer iteration for pagerank 5.6.4 Preconditioning We evaluate (I−βP ̄)−1 or its Neumann series approximation as a precondi- tioner, see section 5.5.3, by examining eigenvalue clustering and matrix-vector multiplies. To understand the preconditioner’s effect on the convergence of Krylov subspace methods, we look at clustering of eigenvalues of the matrix (I − βP ̄)−1(I−αP ̄).Letλi, i=1,...,nbetheeigenvaluesofP ̄.Ifwesolvethe preconditioned iteration defined by (I − βP ̄)−1 exactly, then the eigenval- ues of the matrix P ̄ undergo a Möbius transform to the eigenvalues of the preconditioned system, tion of the eigenvalues is no longer a Möbius transform, but the polynomial pm(λ) = (1 − αλ)(1 + βλ + ⋯ + (βλ)m). (5.26) Of course as m → ∞, we recover the exact preconditioned system. To illustrate the spectral properties of the preconditioned system, figure 5.4 shows the behavior of the preconditioned eigenvalues of two test matrices, for a variety of choices of β and m. In these examples, our preconditioner concentrates the eigenvalues around λ = 1. Solving the system exactly appears unnecessary as we see a strong concentration with even m = 2 or m = 4 terms of the Neumann series, for the values of β we tested. 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. 1 − αλ 1 − βλ . (5.25) p(λ) = When we precondition with only a finite number of terms, then the modifica-PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.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)