Comparison of different ways to solve an underdetermined linear system from Matlab
clc;
clear;
close all;
N=1000; %Rows
MNratio=1.5; %Ratio M/N
M=MNratio*N; %Cols
d=0.2; %Density
S=crandn(N,M).*sprandn(N,M,d);
A=full(S);
b=crandn(N,M);
%% Different ways to solve the underdetermined system Ax=b
tic;
fprintf('-------------------------\n')
fprintf('Sparse MLDIVIDE: non-minimum-norm solution (CHOLMOD algorithm)\n');
%http://www.maths.lth.se/na/courses/NUM115/NUM115-11/backslash.html
x=S\b;
t=toc;
fprintf('norm(A*x-b): %.3g, norm(x): %.3g, time: %.2f seconds\n',norm(A*x-b),norm(x),t)
tic;
fprintf('-------------------------\n')
fprintf('Sparse QR: non-minimum-norm solution\n');
[C,R] = qr(S,b);
x=R\C;
t=toc;
fprintf('norm(A*x-b): %.3g, norm(x): %.3g, time: %.2f seconds\n',norm(A*x-b),norm(x),t)
tic;
fprintf('-------------------------\n')
fprintf('Tim Davis'' sparse spqr_solve: minimum 2-norm solution\n');
% SPQR is part of SuiteSparse http://faculty.cse.tamu.edu/davis/suitesparse.html
x=spqr_solve(S,b, struct ('solution','min2norm'));
t=toc;
fprintf('norm(A*x-b): %.3g, norm(x): %.3g, time: %.2f seconds\n',norm(A*x-b),norm(x),t)
tic;
fprintf('-------------------------\n')
fprintf('Full MLDIVIDE: basic solution\n');
x=A\b;
t=toc;
fprintf('norm(A*x-b): %.3g, norm(x): %.3g, time: %.2f seconds\n',norm(A*x-b),norm(x),t)
tic;
fprintf('-------------------------\n')
fprintf('Full PINV: minimum 2-norm solution\n');
x=pinv(A)*b;
t=toc;
fprintf('norm(A*x-b): %.3g, norm(x): %.3g, time: %.2f seconds\n',norm(A*x-b),norm(x),t)