Main Content

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。您可以使用上述语法中的任意输入参量组合指定两个输出。

示例

全部折叠

打开实时脚本

创建一个由 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 的父级。p(7) 是 0，因为节点 7 是树的根。

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 处的根节点指示。

r = etree(B)
r = 1×6

     2     3     0     5     6     0
打开实时脚本

计算 bucky 稀疏矩阵的两个不同消去树。"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 稀疏矩阵的两种排列的消去树。使用 symrcm 创建对称反向卡西尔-麦基排序，使用 symamd 创建对称近似最小度排序。

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

使用 treeplot 绘制消去树。反向卡西尔-麦基消去树是一排节点，而最小度消去树有多个不相交的分支。

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 可以是满矩阵，也可以是稀疏矩阵。如果消去树类型是 "sym" 或 "lo"，则 A 必须为方阵。etree 使用 A 的稀疏结构来计算消去树。

数据类型: double | logical
复数支持: 是

消去树的类型，指定为 "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(i) 表示树中节点 i 的父级，如果 i 是根节点，则为 0。

消去树 p 的后序排列，以数值向量形式返回。

手动计算乔列斯基分解的列时，可以使用消去树的后序排列。对于消去树 p 中的节点 i 及其父节点 j，在乔列斯基分解中，必须先完全计算出列 i，然后才能计算列 j。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

扩展功能

版本历史记录

在 R2006a 之前推出

另请参阅

| | |