PDF Publication Title:
Text from PDF Page: 046
24 2 ⋅ pagerank background 2.4.1 Important implementation details Let’s begin with a silly question: given a list of positive numbers, how should we compute their sum? Given this task, most people would produce a simple code that resembles the following four lines of Matlab. sumx = 0; for i=1:numel(x) sumx = sumx + x(i); end This routine correctly sums the numbers in exact arithmetic. When computed in floating-point arithmetic, every individual sum contributes an error of at most ε because fl(sumx + x(i))=(1+δ)(sumx + x(i)), ∣δ∣≤ε for some machine ε. After n of these sums, the output sumx has error bounded by nε where n is the number of summands [Higham, 2002]. For a large PageRank problem n ∼ 109 and for double precision arithmetic ε = 2.2⋅10−16, in which case nε is not small. Computing sums is a common operation in PageRank algorithms. We need a better algorithm. Nearly since the dawn of computation, this problem has been studied [Higham, 2002]. (In fact, the reference for the remainder of this section is Higham [2002], which contains an exhaustive treatment of the problem.) The proposed solutions range from phenomenally complicated to subtly simple, and it is the latter approach that is most appropriate for the PageRank context. One of the simplest techniques is called compensated summation. The compensated summation algorithm requires storing one extra floating- point value to accumulate an approximation of the error in the current sum- mation. As given in Higham [2002, section 4.3], the following algorithm is due to Kahan. sumx = 0; err = 0; for i=1:numel(x) temp = sumx; y = x(i) + err; sumx = temp + y; err = (temp - sumx); err = err + y; end % save the current sum % add the error to the summand % increase the sum by the summand and the error % compute the exact difference after adding y % err should be -y, add y to find the true error Instead of nε error, this computation has error 2ε + O(nε2). For most con- ceivable PageRank problems, this accuracy should be sufficient.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 |