Matlab生成稀疏矩阵与稀疏矩阵运算教程

置换与重新排序

可以通过以下两种方式表示稀疏矩阵 S 的行和列置换：

置换矩阵 P 对作为 P*S 的 S 有效，或对作为 S*P' 的列有效。

置换向量 p 是包含 1:n 置换的满向量。对作为 S(p,:) 的 S 行有效，或对作为 S(:,p) 的列有效。

例如：

p = [1 3 4 2 5]

I = eye(5,5);

P = I(p,:)

e = ones(4,1);

S = diag(11:11:55) + diag(e,1) + diag(e,-1)

p =

1 3 4 2 5

P =

1 0 0 0 0

0 0 1 0 0

0 0 0 1 0

0 1 0 0 0

0 0 0 0 1

S =

11 1 0 0 0

1 22 1 0 0

0 1 33 1 0

0 0 1 44 1

0 0 0 1 55

现在，可以使用置换向量 p 和置换矩阵 P 尝试一些置换。例如，语句 S(p,:) 和 P*S 返回相同的矩阵。

S(p,:)

ans =

11 1 0 0 0

0 1 33 1 0

0 0 1 44 1

1 22 1 0 0

0 0 0 1 55

P*S

ans =

11 1 0 0 0

0 1 33 1 0

0 0 1 44 1

1 22 1 0 0

0 0 0 1 55

同样，S(:,p) 和 S*P' 都生成

S*P'

ans =

11 0 0 1 0

1 1 0 22 0

0 33 1 1 0

0 1 44 0 1

0 0 1 0 55

如果 P 是稀疏矩阵，则两种表示形式都使用与 n 成比例的存储，可以在与 nnz(S) 成正比的时间向 S 应用任一种表示形式。向量表示形式略为简洁和有效，因此除了 LU(三角)分解中的主元置换返回与完全 LU 分解兼容的矩阵外，许多稀疏矩阵置换例程都返回满行向量。

要在两种置换表示之间转换：

n = 5;

I = speye(n);

Pr = I(p,:);

Pc = I(:,p);

pc = (1:n)*Pc

pc =

1 3 4 2 5

pr = (Pr*(1:n)')'

pr =

1 3 4 2 5

P 的逆为 R = P'。可以通过 r(p) = 1:n 计算 p 的逆。

r(p) = 1:5

r =

1 4 2 3 5重新排序以改变稀疏性

对矩阵列重新排序通常可以使其 LU 或 QR 因子更加稀疏。对列和列重新排序通常可以使其 Cholesky 因子更加稀疏。此类最简单的重新排序是按照非零元素计数为列排序。对于具有及其不规则结构的矩阵而言，这有时是一个不错的重新排序方法，尤其是行或列的非零元素计数出现重大变化时更是如此。

colperm 函数按每列中非零元素数量从小到大的顺序重排矩阵列，计算矩阵的置换。重新排序以减少带宽

反向 Cuthill-McKee 排序用于减少矩阵的轮廓或带宽。该排序方法不能保证会找到尽可能最小的带宽，但通常都能找到。symrcm 函数实际上处理的是对称矩阵 A + A' 中的非零结构体。但对于非对称矩阵，该函数的结果也很有用。此种排序对源自一维问题或某种意义上细长的问题的矩阵很有用。近似最小度排序

节点在图中的度是到该节点的连接数。这与邻接矩阵的相应行中的非对角非零元素数相同。近似最小度算法基于高斯消去法或 Cholesky 分解期间这些度的更改来进行排序。该算法很复杂并且功能强大，通常会生成比大多数其他排序稀疏的因子，包含列计数和反向 Cuthill-McKee。由于记录每个节点的度非常耗时，因此近似最小度算法使用近似度而不是精确度。

以下 MATLAB® 函数可以实现近似最小度算法：

symamd - 用于对称矩阵。

colamd - 用于 A*A' 或 A'*A 形式的非对称矩阵和对称矩阵。

请参阅稀疏矩阵的重新排序和分解以了解使用 symamd 的示例。

可以使用 spparms 函数更改与这些算法详细信息相关的不同参数。

有关 colamd 和 symamd 所用算法的详细信息，请参阅 [5]。这些算法使用的近似度基于 [1]。嵌套剖分排序

dissect 函数所实现的嵌套剖分排序算法与近似最小度排序类似，即通过将矩阵视为图的邻接矩阵，对矩阵的行和列进行重新排序。该算法通过将图中的顶点对折叠在一起，大幅减小问题的规模。在对较小的图重新排序后，该算法随即通过应用投影和优化步骤，将图恢复至原始大小。

与其他重新排序方法相比，嵌套剖分算法可生成高质量的重新排序，尤其适用于有限元矩阵。有关嵌套剖分排序算法的详细信息，请参阅 [7]。

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删