Main Content

colamd

列近似最小度排列

语法

p = colamd(S)

说明

p = colamd(S) 为稀疏矩阵 S 返回列近似最小度置换向量。对于非对称矩阵 SS(:,p) 可能比 S 具有更稀疏的 LU 因子。S(:,p)' * S(:,p) 的 Cholesky 分解也可能比 S'*S 的 Cholesky 分解稀疏。

knobs 是一个二元素向量。如果 S 是 m×n,则具有超过 (knobs(1))*n 项的行将被忽略。具有超过 (knobs(2))*m 项的列在排序前将被删除,并最后在输出置换 p 中排序。如果 knobs 参数不存在,则 knobs(1) = knobs(2) = spparms('wh_frac')

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)

重复和无序行索引的数目

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

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

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

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

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

示例

全部折叠

由稀疏矩阵组成的 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 contains an object of type line. Axes object 2 with title A(:,p) contains an object of type line.

将原始矩阵的 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) contains an object of type line. Axes object 2 with title lu(A(:,p)) contains an object of type line.

参考

[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 之前推出

另请参阅

| | | |