求解*稀疏*上三角系统

Question

如果我想解决一个完整的上三角系统，我可以拨打linsolve(A,b,'UT')。但是，目前稀疏矩阵不支持这种方式。我该如何克服这一点？

Answer 1

编辑既然你需要的是一个三角形的解决方法，也称为向后/向前替代，可以使用普通的MATLAB反斜线\操作为：

x = U\b 

正如原答复中提到，MATLAB会认识到一个事实，即你的矩阵是三角形。可以肯定的是，您可以将性能与SuiteSparse中的cs_usolve程序进行比较。它是一个用C实现的mex函数，它计算上三角稀疏矩阵的稀疏三角解（这里也有类似的函数：cs_lsolve,cs_utsolve和cs_ltsolve）。

您可以看看原始MATLAB的performance comparison和cs_l(t)solve在稀疏Cholesky分解的上下文中。从本质上讲，MATLAB的性能很好。唯一的缺陷是，如果你想解决一个换位系统

x = U'\b 

MATLAB不不承认，并明确创建的U转置。在这种情况下，您应该明确地呼叫cs_utsolve。

原来的答复如果你的系统是对称的，你只存储上三角矩阵的一部分（这就是我在你的问题理解全），如果Cholesky分解是适合你的，chol处理对称矩阵，如果你的矩阵是肯定的。对于无限矩阵，您可以使用ldl。两者都处理稀疏存储并处理对称矩阵部分。

较新的matlab版本使用cholmod and suitesparse。这是迄今为止我知道的表现最好的Cholesky分解。在matlab中，它也使用平行BALS平行化。

从上述功能得到的因素是上三角矩阵L，使得

A=LL' 

所有你现在需要做的是执行前向和后向代入，这是简单和便宜的。在Matlab这在THA反斜杠操作者

x=L'\(L\b) 

所述基质可以是稀疏的，并且MATLAB将认识到，它是上/下三角自动完成。您还可以将此调用与使用cholesky因式分解所获得因子的正向替换一起使用。

Answer 2

可以使用MLDIVIDE（\）或MRDIVIDE（/）运营商对您的稀疏矩阵...

Answer 3

UT和LT系统是最容易解决的系统之一。请阅读on the wiki。知道这一点，很容易写出你自己的UT或LT解算器：

%# 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 

LT系统的过程非常相似。

话虽如此，它通常是更容易和更快地使用Matlab的反斜线操作：

x = A\b 

这也适用于备用矩阵，如内特已经指出。

请注意，该运算符还可以解决非方形的UT系统A或A在主对角线上有一些等于零的元素（或< eps）。它以最小二乘的方式解决这些情况，这可能会或可能不会让您满意。通过键入

>> help \ 

或

>> help slash 

Matlab的命令提示符

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

了解更多关于（回）斜线操作：您可以检查这些案件执行前解决。