-3

スパース行列で部分ピボットを使用して LU 分解を実行したいと考えています。フル ピボットはスパース マトリックスに対して非常に高速で効率的であり、パーシャル ピボットはスパース マトリックスに対して効率的ではないようです。私の推測では、スパース用にサポートまたは最適化されていないということです。

A=randn(1e4).*(rand(1e4)<0.0001); 
S=sparse(A);

tic; [l,u,p]=lu(A); toc
Elapsed time is 8.699264 seconds.

tic; [l,u,p,q]=lu(S); toc
Elapsed time is 0.006430 seconds.

2 番目のフル ピボットは非常に高速です (1400 倍)。

私の質問は、どうしてですか？マトリックスがまばらな場合、部分ピボット LU はより効率的であり、完全なピボットよりも常に (またはほとんど常に) 高速であるべきではありませんか?

スパース行列で部分ピボットを使用して高速 LU を実行する方法を知っている人はいますか?

ありがとう、ギル

4

1 に答える 1

2

いくつかのことを明確にする必要があるように感じます。

  1. [l u p]スパース マトリックスではなく、バージョンの完全なマトリックスに取り組んでいることを認識していますか?

  2. 部分的なピボットは、パフォーマンスを向上させるためではなく、数値の安定性を得るために使用されます。

  3. 完全なピボットは、疎行列を因数分解するときに発生する塗りつぶしの量を減らすために使用されます (完全な行列では不可能です)。行と列の両方を最適な方法で並べ替えると、パフォーマンスが大幅に向上します。

速度が上がる理由は、非ゼロが対角線に沿って配置されているためです。でも：

「スパースは、エントリの構造と関係があります。対角線の周りのゼロのバンド、その外側のゼロです。」は正しくありません。

スパース行列は、ほとんどゼロを含む行列で、3 つのベクトル (行、列、および値) で表されます。

sparse()完全行列を疎行列に変換する完全に有効な方法です。Duffymo の声明: 「完全な行列を取り、それを疎な行列データ構造にマッピングすると、もちろん遅くなります。」、完全な行列にほとんどゼロが含まれている限り、正しくありません。

次のことを試してください。

S = sprand(100,100,0.01);
[l, u, p] = lu(S);
spy(l)
figure
spy(u)

次に、次の操作を行います。

[ll, uu, pp, qq] = lu(S);
spy(ll);
figure
spy(uu);

lとの構造を見てくださいu。フル ピボットを使用すると速度が向上する理由がわかるかもしれません。

また、実際に高速なのは因数分解部分ではなく、後でこのことを解決しようとするときの前方置換部分です。

于 2013-06-30T11:52:15.913 に答える