Solve the * rare * upper triangular system

Question

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

Answer 1

Change Since you need a three-way solution procedure, also called back / forward substitution, you can use the regular MATLAB \ backslash operator to do this:

 x = U\b 

As mentioned in the original answer, MATLAB recognizes the fact that your matrix is ​​triangular. To verify this, you can compare performance with the cs_usolve procedure found in SuiteSparse . This is a fur function implemented in C that calculates sparse triangular solutions for the upper triangular sparse matrix (there are also similar functions there: cs_lsolve , cs_utsolve and cs_ltsolve ).

You can see a comparison of the performance of native MATLAB and cs_l(t)solve in the context of Cholesky sparse factorization. In fact, MATLAB's performance is good. The only mistake is if you want to solve the transposed system

 x = U'\b 

MATLAB does not recognize this and explicitly creates a transpose of U In this case, you should explicitly call cs_utsolve .

Original answer If your system is symmetric and you save only the upper triangular matrix part (this is how I fully understood your question), and if Cholesky decomposition is suitable for you, chol processes symmetric matrices if your matrix is ​​positive definite. For undefined matrices you can use ldl . Both handle sparse storage and work with symmetric matrix parts.

In newer versions of Matlab for this cholmod and suitesparse . This is, of course, the most effective factorization of Cholesky that I know of. In Matlab, it is also parallelized by parallel BALS.

The factor that you get from the above functions is an upper triangular matrix L such that

 A=LL' 

All you have to do is do forward and reverse replacements, which are simple and cheap. In Matlab, this is automatically done in the backslash statement.

 x=L'\(L\b) 

the matrix can be sparse, and Matlab recognizes that it is upper / lower triangular. You can also use this call in conjunction with directly replacing factors derived from cholesky factorization.

Answer 2

UT and LT systems are some of the easiest systems to solve. Read the wiki about this. Knowing this, it's 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 very similar to LT systems.

Having said that, it’s usually much easier and faster to use the Matlab backslash operator:

 x = A\b 

which also works for spare matrices, as already indicated.

Note that this operator also solves UT systems that have non-quadratic A , or if A has some elements equal to zero (or < eps ) on the main diagonal. He solves these cases in the sense of least squares, which may or may not be desirable for you. You can check these cases before executing the solution:

 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 slash operator (backward) by typing

 >> help \ 

or

 >> help slash 

at the matlab command prompt.

Answer 3

you can use the MLDIVIDE (\) or MRDIVIDE (/) operators on your sparse matrices ...