工具/原料
- matlab软件
- 电脑
方式/步骤
- 1
稀少矩阵的可视化。
间谍图显示矩阵中的非零元素。
这个间谍图显示了一个稀少对称正定矩阵，来自哈韦尔波恩测试矩阵“West0749”的一部门，该矩阵描述了在化工场中的衍射柱模子中的毗连。
号令行键入：
load west0479.mat
A = west0479;
S = A * A' + speye(size(A));
pct = 100 / numel(A);
figure
spy(S)
title('A Sparse Symmetric Matrix')
nz = nnz(S);
xlabel(sprintf('nonzeros = %d (%.3f%%)',nz,nz*pct));
- 2
按”Enter“键。
如图1所示。
- 3
计较乔尔斯基因子。
此刻我们计较乔尔斯基因子L，此中S=L*L‘。
注重，L包含的非零元素比未分化的S要多得多，因为Cholesky因式分化的计较建立了“填充”非零。
这减慢了算法的速度，增添了存储当作本。
tic
L = chol(S,'lower');
t(1) = toc;
spy(L), title('Cholesky decomposition of S')
nc(1) = nnz(L);
xlabel(sprintf('nonzeros = %d (%.2f%%) time = %.2f sec',nc(1),nc(1)*pct,t(1)));
- 4
按”Enter“键。
如图2所示。
- 5
从头排序以加速计较速度
经由过程从头排序矩阵的行和列，可以削减因因因式分化而发生的填充量，从而削减时候和存储当作本。
我们此刻测验考试三种分歧的排序，由MATLAB撑持.
反标的目的切希尔-麦基
列计数
最低水平
利用反标的目的切希尔-麦基
SYMRCM号令利用反标的目的的Cuthill-McKee从头排序算法将所有非零元素移到对角线四周，从而削减了原始矩阵的“带宽”。
号令行键入：
p = symrcm(S);
spy(S(p,p))
title('S(p,p) after Cuthill-McKee ordering')
nz = nnz(S);
xlabel(sprintf('nonzeros = %d (%.3f%%)',nz,nz*pct));
- 6
按”Enter“键。
如图3所示。
- 7
因为Cholesky因式分化发生的填充被限制在带内，使得从头排序后的矩阵因式分化所需的时候更短，存储更少。
号令行键入：
tic
L = chol(S(p,p),'lower');
t(2) = toc;
spy(L)
title('chol(S(p,p)) after Cuthill-McKee ordering')
nc(2) = nnz(L);
xlabel(sprintf('nonzeros = %d (%.2f%%) time = %.2f sec', nc(2),nc(2)*pct,t(2)));
- 8
按”Enter“键。
如图4所示。
- 9
利用列计数
COLPERM号令利用列计数从头排序算法将非零计数更高的行和列移到矩阵的末从头至尾。
号令行键入：
q = colperm(S);
spy(S(q,q)), title('S(q,q) after column count ordering')
nz = nnz(S);
xlabel(sprintf('nonzeros = %d (%.3f%%)',nz,nz*pct));
- 10
按”Enter“键。
如图5所示。
- 11
对于这个示例，列计数挨次正好削减了Cholesky分化的时候和存储量，可是这种行为凡是是无法预料的。
tic
L = chol(S(q,q),'lower');
t(3) = toc;
spy(L)
title('chol(S(q,q)) after column count ordering')
nc(3) = nnz(L);
xlabel(sprintf('nonzeros = %d (%.2f%%) time = %.2f sec',nc(3),nc(3)*pct,t(3)));
- 12
按”Enter“键。
如图6所示。
- 13
利用最小度数。
SYMAMD号令利用近似最小度算法（一种壮大的图论手艺）在矩阵中发生大的零块。
号令行窗口键入：
r = symamd(S);
spy(S(r,r)), title('S(r,r) after minimum degree ordering')
nz = nnz(S);
xlabel(sprintf('nonzeros = %d (%.3f%%)',nz,nz*pct));
- 14
按”Enter“键。
如图7所示。
- 15
最小度算法发生的零块保留在Cholesky分化过程中。
这可以光鲜明显削减时候和存储当作本。
tic
L = chol(S(r,r),'lower');
t(4) = toc;
spy(L)
title('chol(S(r,r)) after minimum degree ordering')
nc(4) = nnz(L);
xlabel(sprintf('nonzeros = %d (%.2f%%) time = %.2f sec',nc(4),nc(4)*pct,t(4)));
- 16
按”Enter“键。
如图8所示。
- 17
总结成果。
号令行键入：
labels = {'original','Cuthill-McKee','column count','min degree'};
ax = subplot(2,1,1);
bar(nc*pct)
title('Nonzeros after Cholesky factorization')
ylabel('Percent');
ax.XTickLabel = labels;
ax = subplot(2,1,2);
bar(t)
title('Time to complete Cholesky factorization')
ylabel('Seconds');
ax.XTickLabel = labels;
- 18
按”Enter“键。
如图9所示。
