Main Content

symamd

对称近似最小度置换

语法

p = symamd(S)
p = symamd(S,knobs)
[p,stats] = symamd(...)

说明

p = symamd(S)(对于对称正定矩阵 S)返回置换向量 p,这样 S(p,p) 倾向于比 S 具有更稀疏的乔列斯基因子。要计算 S 的排序,symamd 构造一个矩阵 M,这样 spones(M'*M) = spones (S),然后计算 p = colamd(M)symamd 函数也可能适用于对称非正定矩阵。

S 必须是方阵;仅引用严格下三角部分。

p = symamd(S,knobs),其中 knobs 为标量。如果 Sn×n,则排序前,将会删除包含多个 knobs*n 项的行和列,并最后在输出置换 p 中排序。如果 knobs 参数不存在,则 knobs = spparms('wh_frac')

[p,stats] = symamd(...) 生成可选的向量 stats,后者提供有关矩阵 S 的排序和有效性的数据。

stats(1)

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

stats(2)

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

stats(3)

symamd 使用的内部数据结构体执行的垃圾回收的次数(大小约等于 8.4*nnz(tril(S,-1)) + 9n 个整数)

stats(4)

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

stats(5)

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

stats(6)

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

stats(7)

重复和无序行索引的数目

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

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

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

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

该排序后跟对称消去树后排序。

示例

全部折叠

此示例是关于反向卡西尔-麦基和最小度与 symrcm 参考页中提及的布基球示例的比较。

B = bucky+4*speye(60);
r = symrcm(B);
p = symamd(B);
R = B(r,r);
S = B(p,p);
subplot(2,2,1), spy(R,4), title('B(r,r)')
subplot(2,2,2), spy(S,4), title('B(s,s)')
subplot(2,2,3), spy(chol(R),4), title('chol(B(r,r))')
subplot(2,2,4), spy(chol(S),4), title('chol(B(s,s))')

Figure contains 4 axes objects. Axes object 1 with title B(r,r), xlabel nz = 240 contains a line object which displays its values using only markers. Axes object 2 with title B(s,s), xlabel nz = 240 contains a line object which displays its values using only markers. Axes object 3 with title chol(B(r,r)), xlabel nz = 514 contains a line object which displays its values using only markers. Axes object 4 with title chol(B(s,s)), xlabel nz = 348 contains a line object which displays its values using only markers.

尽管这是一个很小的问题,但两种排序的行为都很典型。RCM 生成一个具有窄带宽的矩阵,它在乔列斯基分解期间几乎完全填满。最小度算法生成一个包含大块连续零的结构体,这些块在分解期间不进行填充。因此,最小度排序需要的分解时间和存储空间都较少。

参考

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

另请参阅

| | | | |