colamd

列近似最小度排列

语法

p = colamd(S)

说明

p = colamd(S) 为稀疏矩阵 S 返回列近似最小度置换向量。对于非对称矩阵 S，S(:,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.2nnz(S) + 4m + 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 无法继续。将输出一条错误消息，并且不返回任何输出参数（p 或 stats）。

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

示例

全部折叠

比较稀疏矩阵和 LU 分解

打开实时脚本

由稀疏矩阵组成的 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.