Main Content

本页翻译不是最新的。点击此处可查看最新英文版本。

amd

近似最小度置换

语法

P = amd(A)
P = amd(A,opts)

说明

P = amd(A) 为稀疏矩阵 C = A + A' 返回近似最小度置换向量。C(P,P)A(P,P) 的乔列斯基分解可能比 CA 的乔列斯基分解稀疏。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')

示例

全部折叠

在使用 amd 对矩阵进行排序之前和之后计算矩阵的乔列斯基因子,以检查排序操作对稀疏性的影响。

加载杠铃图稀疏矩阵并添加稀疏单位矩阵,以确保它是正定矩阵。计算两个乔列斯基因子:一个属于原始矩阵,另一个属于使用 amd 预先排序后的原始矩阵。

load barbellgraph.mat
A = A+speye(size(A)); 
p = amd(A);
L = chol(A,'lower');
Lp = chol(A(p,p),'lower');

绘制所有四个矩阵的稀疏模式。与自然排序的矩阵相比,从经过预先排序的矩阵获取的乔列斯基因子要稀疏得多。

figure
subplot(2,2,1)
spy(A)
title('Original Matrix A')
subplot(2,2,2) 
spy(A(p,p))
title('AMD ordered A')
subplot(2,2,3) 
spy(L)
title('Cholesky factor of A')
subplot(2,2,4) 
spy(Lp)
title('Cholesky factor of AMD ordered A')

Figure contains 4 axes objects. axes object 1 with title Original Matrix A, xlabel nz = 18441 contains a line object which displays its values using only markers. axes object 2 with title AMD ordered A, xlabel nz = 18441 contains a line object which displays its values using only markers. axes object 3 with title Cholesky factor of A, xlabel nz = 606297 contains a line object which displays its values using only markers. axes object 4 with title Cholesky factor of AMD ordered A, xlabel nz = 52988 contains a line object which displays its values using only markers.

参考

[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.

扩展功能

另请参阅

| | | |