Solve *sparse* upper triangular system

Question

If I want to solve a full upper triangular system, I can call linsolve(A,b,'UT'). However this currently is not supported for sparse matrices. How can I overcome this?

Answer 1

UT and LT systems are amongst the easiest systems to solve. Have a read on the wiki about it. Knowing this, it is easy to write your own UT or LT solver:

%# some example data
A = sparse( triu(rand(100)) );
b = rand(100,1);

%# solve UT system by back substitution    
x = zeros(size(b));
for n = size(A,1):-1:1    
    x(n) = (b(n) - A(n,n+1:end)*x(n+1:end) ) / A(n,n);    
end

The procedure is quite similar for LT systems.

Having said that, it is generally much easier and faster to use Matlab's backslash operator:

x = A\b

which also works for spares matrices, as nate already indicated.

Note that this operator also solves UT systems which have non-square A or if A has some elements equal to zero (or < eps) on the main diagonal. It solves these cases in a least-squares sense, which may or may not be desirable for you. You could check for these cases before carrying out the solve:

if size(A,1)==size(A,2) && all(abs(diag(A)) > eps)
    x = A\b;
else
    %# error, warning, whatever you want
end

Read more about the (back)slash operator by typing

>> help \

or

>> help slash

on the Matlab command prompt.