置换与重新排序
可以通过以下两种方式表示稀疏矩阵 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]。