etree

消去木

構文

p = etree(A)

p = etree(A,type)

[p,q] = etree(___)

説明

p = etree(A) は、A と同じ上三角をもつ対称正方行列の消去木を返します。

p = etree(A,type) は消去木のタイプを指定します。たとえば、type が "lo" の場合、etree は A の下三角を使用して対称正方行列を作成します。

[p,q] = etree(___) は、消去木の降順置換 q も返します。2 つの出力は、前述の構文に示した任意の入力引数の組み合わせを使用して指定できます。

例

行列の消去木

0 と 1 から成る 7 行 7 列の三重対角行列を作成します。

A = diag(ones(1,7)) + diag(ones(1,6),1) + diag(ones(1,6),-1)

A = 7×7

     1     1     0     0     0     0     0
     1     1     1     0     0     0     0
     0     1     1     1     0     0     0
     0     0     1     1     1     0     0
     0     0     0     1     1     1     0
     0     0     0     0     1     1     1
     0     0     0     0     0     1     1

A の消去木を計算します。消去木の各要素 p(i) は、ノード i の親を表します。ノード 7 が木のルートであるため、p(7) は 0 です。

p = etree(A)

p = 1×7

     2     3     4     5     6     7     0

0 と 1 から成る 6 行 6 列のブロック対角行列を作成します。

a = ones(3);
b = zeros(3);
B = [a b; b a]

B = 6×6

     1     1     1     0     0     0
     1     1     1     0     0     0
     1     1     1     0     0     0
     0     0     0     1     1     1
     0     0     0     1     1     1
     0     0     0     1     1     1

B の消去木を計算します。etree は、インデックス 3 および 6 のルート ノードによって示された 2 つの消去木をもつ森を返します。

r = etree(B)

r = 1×6

     2     3     0     5     6     0

消去木のタイプの指定

スパース行列 bucky の 2 つの異なる消去木を計算します。"lo" 消去木は A の下三角を使用します。一方、"col" 消去木は行列 A'*A を使用します。

A = bucky;
p1 = etree(A,"lo");
p2 = etree(A,"col");

treeplot を使用して消去木をプロットします。

treeplot(p1)
title("Lower Triangle Elimination Tree")

treeplot(p2)
title("Column Elimination Tree")

スパース パターンの異なる消去木

スパース行列 bucky の 2 つの置換の消去木を計算します。symrcm を使用して対称逆 Cuthill-McKee での並べ替えを作成し、symamd を使用して対称な近似最小次数の並べ替えを作成します。

A = bucky;
r = symrcm(A);
p1 = etree(A(r,r));
m = symamd(A);
p2 = etree(A(m,m));

treeplot を使用して消去木をプロットします。逆 Cuthill-McKee 消去木はノードのラインです。一方、最小次数消去木には複数の別個の分岐があります。

treeplot(p1)
title("Reverse Cuthill-McKee Elimination Tree")

treeplot(p2)
title("Minimum Degree Elimination Tree")

spy を使用してスパース パターンをプロットします。行列の消去木はスパース パターンによって異なるため、スパース パターンが異なれば別の消去木になります。

spy(A(r,r))
title("Reverse Cuthill-McKee Sparsity Pattern")

spy(A(m,m))
title("Minimum Degree Sparsity Pattern")

入力引数

A — 入力行列

行列

入力行列。A は非スパースまたはスパースのいずれでもかまいません。消去木のタイプが "sym" または "lo" の場合、A は正方行列でなければなりません。etree は A のスパース構造を使用して消去木を計算します。

データ型: double | logical
複素数のサポート: あり

type — 消去木のタイプ

"sym" (既定値) | "lo" | "col" | "row"

消去木のタイプ。"sym"、"lo"、"col"、または "row" として指定します。この引数を使用して、行列 etree が何を使用して消去木を計算するのかを指定します。

• type が "sym" の場合、etree は A の上三角を使用して対称正方行列を作成し、その行列の消去木を返します。

• type が "lo" の場合、etree は A の下三角を使用して対称正方行列を作成し、その行列の消去木を返します。

• type が "col" の場合、etree は行列 A'*A を作成し、その行列の消去木を返します。これは、A の列の消去木です。

• type が "row" の場合、etree は行列 A*A' を作成し、その行列の消去木を返します。これは、A の行の消去木です。

出力引数

p — 消去木

数値ベクトル

消去木。数値ベクトルとして返されます。p(i) は木のノード i の親または 0 (i が根の場合) を表します。

q — 降順置換

数値ベクトル

消去木 p の降順置換。数値ベクトルとして返されます。

コレスキー分解の列を手計算する際に、消去木の降順置換を使用できます。コレスキー分解では、消去木 p のノード i およびその親ノード j について、列 j の前に列 i を完全に計算する必要があります。p の降順置換は、該当する列を計算する、この要件に整合した順序を指定します。chol を使用して因数分解を直接計算します。

詳細

消去木

消去木は、コレスキー分解の行と列の依存関係を取得し、同時に実行できる演算を記述するデータ構造です。消去木の別個の分岐を並列計算できるため、分岐のある消去木をもつ行列の因数分解をより高速に計算できます。スパース行列を並べ替えて非スパース要素数を変更し、異なる消去木を計算できます。

参照

[1] Chen, Yanqing, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. “Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate.” ACM Transactions on Mathematical Software 35, no. 3 (October 2008): 1–14. https://doi.org/10.1145/1391989.1391995.

[2] Pothen, Alex, and Sivan Toledo. "Elimination Structures in Scientific Computing." In Handbook of Data Structures and Applications, edited by Dinesh P. Mehta and Sartaj Sahni, 945–965. New York: Chapman and Hall/CRC, 2017. https://doi.org/10.1201/9781315119335

拡張機能

スレッドベースの環境

MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

この関数はスレッドベースの環境を完全にサポートしています。詳細については、スレッドベースの環境での MATLAB 関数の実行を参照してください。

バージョン履歴

R2006a より前に導入

参考

chol | treelayout | etreeplot | treeplot