ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

スパース行列の並べ替え

この例では、スパース行列の行と列を並べ替えると、行列操作の要件である速度とストレージにどのような影響を与えるかを示します。

スパース行列の可視化

spy プロットは、行列の非ゼロ要素を示します。

この spy プロットは、Harwell-Boeing のテスト行列 west0479 の一部から派生するスパース正定値対称行列を示します。この行列は、化学プラントにおける回折列のモデル内での連結を記述します。

load west0479.mat
A = west0479;
S = A * A' + speye(size(A));
pct = 100 / numel(A);

spy(S)
title('A Sparse Symmetric Matrix')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

コレスキー因子の計算

S = L*L' の場合のコレスキー因子 L の計算。コレスキー分解の計算では非スパース (非ゼロ) が発生するため、L には、分解されていない S よりもかなり "多く" の非ゼロ要素が含まれます。これらの非スパース値はアルゴリズム速度を低下させ、ストレージ コストを増加させます。

L = chol(S,'lower');
spy(L)
title('Cholesky Decomposition of S')
nc(1) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(1),nc(1)*pct));

並べ替えによる計算の高速化

行列の行と列を並べ替えることで、分解で得られる非スパースの量を減らし、それにより時間とストレージ コストの削減ができます。

MATLAB® によってサポートされる 3 種類の並べ替えを次に示します。

  • 逆 Cuthill-McKee 法

  • 列カウント法

  • 最小次数法

west0479 行列でのこれらのスパース行列の並べ替えの効果をテストします。

並べ替え 1: 逆 Cuthill-McKee 法

symrcm コマンドは、すべての非ゼロ要素を対角要素の近くに移動させ、元の行列のバンド幅を小さくする、逆 Cuthill-McKee 並べ替えアルゴリズムを使用します。

p = symrcm(S);
spy(S(p,p))
title('S(p,p) After Cuthill-McKee Ordering')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

並べ替えを行った行列の分解には時間とストレージがあまりかからないように、コレスキー分解によって得られる非スパースは帯上のみに限られます。

L = chol(S(p,p),'lower');
spy(L)
title('chol(S(p,p)) After Cuthill-McKee Ordering')
nc(2) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)', nc(2),nc(2)*pct));

並べ替え 2: 列カウント法

colperm コマンドは、列カウント並べ替えアルゴリズムを使用して、非ゼロ要素数のより多い行と列を行列の最後に移動します。

q = colperm(S);
spy(S(q,q))
title('S(q,q) After Column Count Ordering')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

この行列では、列数の並べ替えによってコレスキー分解にかかる時間とストレージが減少しますが、これは一般的には保証されません。

L = chol(S(q,q),'lower');
spy(L)
title('chol(S(q,q)) After Column Count Ordering')
nc(3) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(3),nc(3)*pct));

並べ替え 3: 最小次数法

symamd コマンドは、近似最小次数アルゴリズム (強力なグラフ理論の手法) を使用して、行列の中に大きな 0 のブロックを作成します。

r = symamd(S);
spy(S(r,r))
title('S(r,r) After Minimum Degree Ordering')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

コレスキー分解は、最小次数アルゴリズムによって得られた 0 のブロックを保持します。この構造により、時間とストレージ コストを大幅に削減できます。

L = chol(S(r,r),'lower');
spy(L)
title('chol(S(r,r)) After Minimum Degree Ordering')
nc(4) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(4),nc(4)*pct));

結果のまとめ

この棒グラフは、コレスキー分解を実行する前の行列の並べ替えの効果をまとめています。元の行列のコレスキー分解の約 13% が非ゼロの要素だった場合、symamd を使用するとその密度はわずか 4% に削減されます。

labels = {'Original','Cuthill-McKee','Column Count','Min Degree'};
bar(nc*pct)
title('Nonzeros After Cholesky Factorization')
ylabel('Percent');
ax = gca;
ax.XTickLabel = labels;
ax.XTickLabelRotation = -45;

参考

| | | | |