matlab - *スパース*上三角システムを解く

Question

完全な上三角システムを解きたい場合は、を呼び出すことができますlinsolve(A,b,'UT')。ただし、これは現在、スパース行列ではサポートされていません。どうすればこれを克服できますか？

Answer 1

UTおよびLTシステムは、最も簡単に解決できるシステムの1つです。それについてウィキを読んでください。これを知っていると、独自の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場合のUTシステムも解くことに注意してください。最小二乗の意味でこれらのケースを解決しますが、これはあなたにとって望ましい場合と望ましくない場合があります。解決を実行する前に、これらのケースを確認できます。A< eps

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

次のように入力して、（バック）スラッシュ演算子の詳細を読む

>> help \

また

>> help slash

Matlabコマンドプロンプトで。

Answer 2

編集必要なのは、後方/前方置換とも呼ばれる三角形の解決手順であるため、通常の MATLAB バックスラッシュ\演算子を使用できます。

x = U\b

元の回答で述べたように、MATLAB は行列が三角形であるという事実を認識します。それを確認するために、パフォーマンスをSuiteSparsecs_usolveにあるプロシージャと比較できます。これは、C で実装された mex 関数であり、上三角疎行列の疎三角解法を計算します (同様の関数もあります: 、および)。cs_lsolvecs_utsolvecs_ltsolve

ネイティブ MATLAB とスパース コレスキー分解のコンテキストでのパフォーマンス比較を見ることができます。cs_l(t)solve基本的に、MATLAB のパフォーマンスは良好です。唯一の落とし穴は、転置されたシステムを解決したい場合です

x = U'\b

MATLAB はそれを認識せずU、明示的に の転置を作成します。その場合、cs_utsolve明示的に呼び出す必要があります。

元の回答システムが対称で、上三角行列部分のみを格納する場合 (つまり、質問で完全に理解した方法です)、コレスキー分解が適している場合、行列が正定の場合、 cholは対称行列を処理します。不定行列の場合、ldlを使用できます。どちらもスパース ストレージを処理し、対称行列の部分を操作します。

新しい matlab バージョンでは、 cholmod と suitesparseを使用しています。これは、私が知る中で最も優れたコレスキー分解です。matlab では、並列 BALS を使用して並列化されます。

上記の関数から得られる係数は、次のような上三角行列 L です。

A=LL'

ここで行う必要があるのは、単純で安価な前方置換と後方置換を実行することだけです。matlab では、これはバックスラッシュ演算子で自動的に行われます

x=L'\(L\b)

行列は疎である可能性があり、matlab はそれが上/下三角であることを認識します。この呼び出しは、コレスキー因数分解を使用して取得された因数の前方置換と共に使用することもできます。

Answer 3

スパース行列でMLDIVIDE（\）またはMRDIVIDE（/）演算子を使用できます。