稀疏矩阵重新排序
此示例展示了对稀疏矩阵的行和列重新排序如何影响矩阵操作的速度和存储需求。
可视化稀疏矩阵
SPY图显示了矩阵中的非零元素。
这个间谍阴谋显示了一个稀疏对称正定矩阵，它来自Harwell-Boeing测试矩阵“west0479”的一部分，这个矩阵描述了化工厂中一个衍射柱模型中的连接。
负载west0479.mat一个= west0479;S = A * A' + speye(size(A));pct = 100 / numel(A);图间谍(S)标题(“一个稀疏对称矩阵”) nz = nnz(S);包含(sprintf ('非零= %d (%.3f%%)'，新西兰，新西兰*pct）；
计算Cholesky因子
现在我们计算Cholesky因子L，其中S = L*L'。注意，L包含的非零元素比未分解的S多得多，因为Cholesky分解的计算创建了“填充”非零。这降低了算法的速度，增加了存储成本。
tic L = chol(S，“低”）;t (1) = toc;间谍(L)、标题(S的Cholesky分解) nc(1) = nnz(L);包含(sprintf (= %d (%.2f%%) time = %。2 f交会”、数控(1)、数控(1)* pct, t (1)));
重新排序以加速计算
通过对矩阵的行和列重新排序，可以减少因式分解产生的填充量，从而减少时间和存储成本。
现在，我们将尝试MATLAB®支持的三种不同顺序。万博1manbetx
反向Cuthill-McKee
列数
最低程度上
使用反向卡希尔麦基
SYMRCM命令使用反向Cuthill-McKee重排算法将所有非零元素移向对角线，从而减少原始矩阵的“带宽”。
p = symrcm(年代);间谍(S (p, p))标题('S(p,p) after Cuthill-McKee ordered ') nz = nnz(S);包含(sprintf ('非零= %d (%.3f%%)'，新西兰，新西兰*pct）；
Cholesky分解所产生的填充被限制在带内，使得对重排序矩阵进行分解所花费的时间和存储空间更小。
tic L=胆固醇（S（p，p），“低”）;t (2) = toc;间谍(L)标题(“Cuthill-McKee命令后的chol（S（p，p））”) nc(2) = nnz(L);包含(sprintf (= %d (%.2f%%) time = %。2 f交会”、数控(2)、数控(2)* pct, t (2)));
使用列计数
COLPERM命令使用列计数重排算法将计数较高的行和列移到矩阵的末尾。
q = colperm(年代);间谍(S (q, q)),标题('S(q,q)后列计数排序') nz = nnz(S);包含(sprintf ('非零= %d (%.3f%%)'，新西兰，新西兰*pct）；
对于本例，列计数排序恰好减少了Cholesky分解所需的时间和存储空间，但一般情况下不能预期这种行为。
tic L = chol(S(q,q)，“低”）;t (3) = toc;间谍(L)标题('chol(S(q,q))在列数排序后') nc(3) = nnz(L);包含(sprintf (= %d (%.2f%%) time = %。2 f交会”、数控(3)、数控(3)* pct, t (3)));
使用最低程度
SYMAMD命令使用近似最小度算法(一种强大的图论技术)在矩阵中生成大的零块。
r = symamd(年代);间谍(S (r, r)),标题(最小度排序后的S（r，r）) nz = nnz(S);包含(sprintf ('非零= %d (%.3f%%)'，新西兰，新西兰*pct）；
在切尔斯基分解过程中保留了最小次算法产生的零块。这可以显著减少时间和存储成本。
tic L = chol(S(r,r)，“低”）;t (4) = toc;间谍(L)标题('chol(S(r,r))在最低学位排序后') nc(4) = nnz(L);包含(sprintf (= %d (%.2f%%) time = %。2 f交会”、数控(4)、数控(4)* pct, t (4)));
总结结果
标签= {“原始”，“Cuthill-McKee”，“列数”，“最低学位”};酒吧(数控* pct)标题(“Cholesky分解后的非零”)伊拉贝尔(“百分比”）;甘氨胆酸ax =;斧子。XTickLabel =标签;
这个话题有用吗?
你也可以从以下列表中选择一个网站:
