Main Content

本页对应的英文页面已更新,但尚未翻译。 若要查看最新内容,请点击此处访问英文页面。

symamd

对称近似最小度置换

语法

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

说明

p = symamd(S)(对于对称正定矩阵 S)返回置换向量 p,这样 S(p,p) 倾向于比 S 具有更稀疏的 Cholesky 因子。要计算 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)。

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

示例

全部折叠

此示例是关于反向 Cuthill-McKee 和最小度与 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))')

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

参考

symamd 的代码作者为佛罗里达大学的 Stefan I. Larimore 和 Timothy A. Davis (davis@cise.ufl.edu)。算法通过与 John Gilbert、Xerox PARC 和 Esmond Ng, Oak Ridge 国家实验室协作开发完成。佛罗里达大学的稀疏矩阵算法研究:https://www.cise.ufl.edu/research/sparse/

另请参阅

| | | | |

在 R2006a 之前推出