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. Axes 1 with title A contains an object of type line. Axes 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. Axes 1 with title lu(A) contains an object of type line. Axes 2 with title lu(A(:,p)) contains an object of type line.

参考

[1] The authors of the code for colamd are Stefan I. Larimore and Timothy A. Davis. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory. Sparse Matrix Algorithms Research: https://people.engr.tamu.edu/davis/research.html