amd
近似最小度置换
语法
P = amd(A)
P = amd(A,opts)
说明
P = amd(A)
为稀疏矩阵 C = A + A'
返回近似最小度置换向量。C(P,P)
或 A(P,P)
的乔列斯基分解可能比 C
或 A
的乔列斯基分解稀疏。amd
函数可能比 symamd
函数快,还可能比 symamd
返回更好的排序。矩阵 A
必须是方阵。如果 A
为满矩阵,则 amd(A)
等效于 amd(sparse(A))
。
P = amd(A,opts)
允许使用更多的重新排序选项。opts
输入是具有如下所示两个字段的结构体。只需设置相关字段:
dense - 指示视为稠密项的非负标量值。如果 A 为 n×n,则
A + A'
中具有多于max(16,(dense*sqrt(n)))
个条目的行和列被视为“稠密”项并在排序期间忽略。MATLAB® 软件将这些行和列放在输出的置换形式的最后。如果未显示此选项,则此字段的默认值为 10.0。aggressive - 控制主动吸收的标量值。如果此字段设置为非零值,则执行主动吸收。如果未显示此选项,这就是默认值。
MATLAB 软件执行装配树后排序,此运算通常与消去树后排序相同。由于使用了近似度更新,且“稠密”行和列不参与后排序,因此二者有时存在差异。此方法非常适合于后续的 chol
运算,但如果您需要执行精确消去树后排序,可以使用以下代码:
P = amd(S); C = spones(S)+spones(S'); [ignore, Q] = etree(C(P,P)); P = P(Q);
如果 S
已对称,请忽略第二行 C = spones(S)+spones(S')
。
示例
参考
[1] Amestoy, Patrick R., Timothy A. Davis, and Iain S. Duff. “Algorithm 837: AMD, an Approximate Minimum Degree Ordering Algorithm.” ACM Transactions on Mathematical Software 30, no. 3 (September 2004): 381–388. https://doi.org/10.1145/1024074.1024081.