求解*稀疏*上三角系統

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 

瞭解更多關於（回）斜線操作：您可以檢查這些案件執行前解決。