它取决于域的形状和局部细化的存在，但对于维度的各向同性域，可实现的最小带宽缩放为其中是元素的总数（或顶点）。您可以使用像Reverse Cuthill-McKee这样的方法来生成合理的低带宽排序。$d$$N^{\frac{d-1}{d}}$$N$

然而，最小化带宽并不是稀疏直接求解器排序技术的目标。实际上，这将导致非零，但最佳排序（通常通过大多数包使用的嵌套剖析等排序找到）具有非零在 2D 中和在 3D 中非零。有关此结果的详细信息，请参见George、Liu 和 Ng 的书。$N^{\frac{2d-1}{d}}$$N \log N$$N^{4/3}$

订单的视觉比较

下面以图形方式比较了规则网格上的 5 点拉普拉斯算子的排序。对于每个排序，我报告了网格和因子中的非零数。请注意，这种差异在 3D 中更为明显。您可以使用 PETSc 绘制填充矩阵和诊断：$12\times 12$$L$$U$$100\times 100$

$ cd $PETSC_DIR/src/ksp/ksp/examples/tutorials && make ex2  

$ ./ex2 -m 12 -n 12 -ksp_view -pc_type lu -pc_factor_mat_ordering_type nd -mat_view_draw -draw_pause 2

自然排序中的矩阵和因子（1990198 个非零）$A$$L$

逆 Cuthill-McKee 排序中的矩阵和因子（1353100 个非零）$A$$L$

嵌套剖析排序中的矩阵和因子（382934 个非零）$A$$L$

另一方面，低带宽排序对于不完全分解和松弛（如 SOR）通常是合理的排序（在算法上），并且倾向于很好地重用缓存（因此有利于吞吐量）。为了在结构化网格上获得最大性能，您可以跳过列索引（因为它们具有规则结构）并仅存储模板系数，甚至可以即时重新计算系数。非常值得使用性能模型进行仔细的剖析和分析，以确定这样的优化是否值得花费实施时间和降低灵活性。

重新排序算法的比较以及它们对迭代求解器的影响也在这里（向下几页）：

http://www.dealii.org/developer/doxygen/deal.II/namespaceDoFRenumbering.html