Main Content

本页翻译不是最新的。点击此处可查看最新英文版本。

colamd

列近似最小度排列

说明

示例

p = colamd(S) 为稀疏矩阵 S 返回列近似最小度置换向量。

p = colamd(S,knobs) 指定 S 的行和列中最大条目数的阈值,超过该阈值则忽略行或列。

[p,stats] = colamd(___) 指定附加输出 stats,该输出提供有关矩阵 S 的排序和有效性的数据。

示例

全部折叠

由稀疏矩阵组成的 Harwell-Boeing 集合和 MATLAB® demos 目录包含测试矩阵 west0479。它是一个 479 阶的矩阵,产生于八个阶段的化工精馏塔的 Westerberg 模型。spy 图显示了八个阶段的证据。colamd 排序使此结构体变得混乱。

load west0479
A = west0479;
p = colamd(A);

figure()
subplot(1,2,1), spy(A,4), title('A')
subplot(1,2,2), spy(A(:,p),4), title('A(:,p)')

Figure contains 2 axes objects. axes object 1 with title A, xlabel nz = 1887 contains a line object which displays its values using only markers. axes object 2 with title A(:,p), xlabel nz = 1887 contains a line object which displays its values using only markers.

将原始矩阵的 LU 分解的 spy 图与重新排序后的矩阵的 spy 图进行比较,结果表明最小度比因子为 2.8 时降低了时间和存储要求。非零计数分别为 15918 和 5920。

figure()
subplot(1,2,1), spy(lu(A),4), title('lu(A)')
subplot(1,2,2), spy(lu(A(:,p)),4), title('lu(A(:,p))')

Figure contains 2 axes objects. axes object 1 with title lu(A), xlabel nz = 15918 contains a line object which displays its values using only markers. axes object 2 with title lu(A(:,p)), xlabel nz = 5920 contains a line object which displays its values using only markers.

输入参数

全部折叠

稀疏矩阵。尽管 MATLAB® 的内置函数生成有效的稀疏矩阵,但可能会使用 MATLAB C 或 Fortran API 构造一个无效稀疏矩阵并将其传递给 colamd。因此,colamd 验证 S 是否为有效的稀疏矩阵:

  • 如果一个行索引在同一列中出现两次或以上,colamd 将忽略重复项,继续处理,并提供有关 stats(4:7) 中的重复项的信息。

  • 如果列中的行索引是无序的,colamd 将对矩阵 S 的内部副本的每列进行排序(但不会修复输入矩阵 S),继续处理,并提供有关 stats(4:7) 中的无序项的信息。

  • 如果 S 始终无效,colamd 无法继续。将输出一条错误消息,并且不返回任何输出参量(pstats)。

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

行和列阈值,指定为向量。knobs 可以有一到三个元素:

  • 超出 max(16,knobs(1)*sqrt(size(S,2))) 个项的行将被忽略。

  • 具有超过 max(16,knobs(2)*sqrt(min(size(S)))) 项的列最后在输出置换 p 中排序。

  • 如果 knobs(1)knobs(2) 小于 0,则分别只删除完全稠密的行或列。

  • 如果 knobs(3) 不为零,则打印 statsknobs

示例: p = colamd(S,[10 5])

输出参量

全部折叠

置换向量,以数值向量形式返回。对于非对称矩阵 SS(:,p) 可能比 S 具有更稀疏的 LU 因子。S(:,p)'*S(:,p) 的 Cholesky 分解也可能比 S'*S 的 Cholesky 分解稀疏。

该排序后跟列消去树后排序。

排序信息,以向量形式返回。stats 向量包含关于所执行的排序和关于稀疏输入矩阵 S 的信息:

stats(1)

colamd 忽略的密集或空行的数目

stats(2)

colamd 忽略的密集或空列的数目

stats(3)

colamd 使用的内部数据结构体执行的垃圾回收的次数(大小约等于 2.2*nnz(S) + 4*m + 7*n 个整数)

stats(4)

0(如果矩阵有效)或 1(如果无效)

stats(5)

未排序或包含重复项的最右侧列的索引,或者为 0(如果不存在此类列)

stats(6)

stats(5) 指定的列索引中上次看到的重复或无序行索引,或者为 0(如果不存在此类行索引)

stats(7)

重复和无序行索引的数目

元素 stats(4:7) 仅与使用 MATLAB C 或 Fortran API 构造的输入矩阵 S 相关。在这种情况下,元素诊断这种矩阵是否具有无效格式。有关详细信息,请参阅 S 的描述。

参考

[1] Davis, Timothy A., John R. Gilbert, Stefan I. Larimore, and Esmond G. Ng. “Algorithm 836: COLAMD, a Column Approximate Minimum Degree Ordering Algorithm.” ACM Transactions on Mathematical Software 30, no. 3 (September 2004): 377–380. https://doi.org/10.1145/1024074.1024080.

扩展功能

版本历史记录

在 R2006a 之前推出

另请参阅

| | | |