% Runtime measurements for solution of \emph{dense} linear least squares
% problem in MATLAB
m = 5; % Number of unknowns (width of matrix)
N = 4000; % maximum height of matrix
A = rand(N,m); % initialize a random matrix
v = rand(N,1); % initialize random right hand side vector

res = []; % matrix for collecting the results
for i=10:10:N
    B = A(1:i,:);   % extract submatrix
    w = v(1:i);     % extract subvector 
    t = realmax;
    % measure time it takes to solve least squares problem. Note that the
    % $\backslash$-operators triggers solution of linear least squares problem,
    % because we deal an underdetermined system
    for j=1:3, tic; z = B\w; t = min(toc,t); end
    res = [res; i, t];
end

figure; plot(res(:,1),res(:,2),'r+',...
    res(:,1),res(:,1).^1/(res(end,1)^1)*res(end,2),'k-');
xlabel('{\bf No. of equations}','fontsize',14);
ylabel('{\bf time [s]}','fontsize',14);
title('Runtime for solving least squares problem with 5 unknowns');
legend('runtime [s]','O(n)','location','best');

print -depsc2 '../../LANMFigures/lsqtiming.eps';
