%MATLAB script: Wasteful and efficient matrix-vector multiplication with a
%matrix whose upper triangle is all 1: runtime measurements
N = 3000;
% Build dense matrix, \texttt{triu} extracts upper triangular part of a
% matrix (see MATLAB documentation for details)
T = triu(ones(N,N));
v = rand(N,1); % Initialize random vector

res = []; % Matrix for storing runtimes
for n=10:10:N
    M = T(1:n,1:n); % obtain $n\times n$ submatrix by index range access
    w = v(1:n);     % isolate first $n$ vector components
    % Direct multiplication with matrix, \textbf{effort = $O(n^2)$} !
    t1 = realmax; for j=1:3, tic; z1 = M*w; t1 = min(t1,toc); end
    % Plain summation of vector components, \textbf{effort = $O(n)$} !
    t2 = realmax;
    for j=1:3
        tic;    
        z2 = zeros(n,1); z2(n) = w(n);
        for k=n-1:-1:1, z2(k) = z2(k+1)+w(k); end
        t2 = min(t2,toc);
    end
    norm(z1-z2), % Check whether the results are the same
    % Record runtimes in the matrix \texttt{res}
    res = [res; n,t1,t2];
end

% Graphical output of runtimes
figure; 
plot(res(:,1),res(:,2),'b+',res(:,1),res(:,3),'r.');
xlabel('{\bf vector length n}','fontsize',14);
ylabel('{\bf runtime [s]}','fontsize',14);
title('runtime measurements: multiplication upper triangular 1-matrix');
legend('matrix multiplication','cumulative summation','location','best');
% Store plot in vector graphics format (EPS)
print -depsc2 '../../LANMFigures/onetriumatvec.eps'; 
