# PageRank

(Difference between revisions)
 Revision as of 20:27, 17 February 2009 (edit)← Previous diff Revision as of 20:49, 17 February 2009 (edit) (undo)Next diff → Line 1: Line 1: + [[Image:Gleich.jpg|thumb|right|793px|CSUM in Digital Signal Processing terms]]

function s=csum(x)                                                                                                                            function s=csum(x)
% CSUM Sum of elements using a compensated summation algorithm                                                                                % CSUM Sum of elements using a compensated summation algorithm
%                                                                                                                                             %
-                                                             % For large vectors, the native sum command in Matlab does not appear to     +                                                                % For large vectors, the native sum command in Matlab does
-                                                             % use a compensated summation algorithm which can cause significant round    +                                                                % not appear to use a compensated summation algorithm which
-                                                             % off errors.                                                                +                                                                % can cause significant roundoff errors.
%                                                                                                                                             %
-                                                             % This code implements a variant of Kahan's compensated summation algorithm  +                                                                % This code implements a variant of Kahan's compensated
-                                                             % which often takes about twice as long, but produces more accurate sums     +                                                                % summation algorithm which often takes about twice as long,
-                                                             % when the number of elements is large.                                      +                                                                % but produces more accurate sums when the number of
+                                                                % elements is large.
%                                                                                                                                             %
Line 21:                                                                                                                                   Line 23:
% David Gleich, Stanford University, 2008                                                                                                     % David Gleich, Stanford University, 2008

-                                                             shat=0; y=0; e=0;                                                            +                                                                s_hat=0; y=0; e=0;
for i=1:numel(x)                                                                                                                              for i=1:numel(x)
-                                                             shat_old = shat;                                                             +                                                                s_hat_old = s_hat;
y = x(i) + e;                                                                                                                                 y = x(i) + e;
-                                                             shat = shat_old + y;                                                         +                                                                s_hat = s_hat_old + y;
-                                                             e = (shat_old - shat) + y;                                                   +                                                                e = (s_hat_old - s_hat) + y;
end                                                                                                                                           end

## Revision as of 20:49, 17 February 2009

```function s=csum(x)
% CSUM Sum of elements using a compensated summation algorithm
%
% For large vectors, the native sum command in Matlab does
% not appear to use a compensated summation algorithm which
% can cause significant roundoff errors.
%
% This code implements a variant of Kahan's compensated
% summation algorithm which often takes about twice as long,
% but produces more accurate sums when the number of
% elements is large.
%
%
% Example:
%   v=rand(1e7,1);
%   sum1 = sum(v);
%   sum2 = csum(v);
%   fprintf('sum1 = %18.16e\nsum2 = %18.16e\n', sum1, sum2);

% David Gleich, Stanford University, 2008

s_hat=0; y=0; e=0;
for i=1:numel(x)
s_hat_old = s_hat;
y = x(i) + e;
s_hat = s_hat_old + y;
e = (s_hat_old - s_hat) + y;
end
```