考虑一个正方形$N \times N$块矩阵$\mathbf{A}$，其中每个$n \times n$块$\mathbf{A}_{ii}$要么是密集块，要么是零块。因此，$N$表示块的数量，$n$表示每个正方形块的大小。

随机示例：

$$\mathbf{A}=\left[ \begin{array}{ccccc} \mathbf{A}_{11} & \mathbf{0} & \mathbf{A}_{13} & \mathbf{A}_{14} & \mathbf{0} \\ \mathbf{A}_{21} & \mathbf{A}_{22} & \mathbf{0} & \mathbf{0} & \mathbf{A}_{25} \\ \mathbf{0} & \mathbf{0} & \mathbf{A}_{33} & \mathbf{A}_{34} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{A}_{43} & \mathbf{A}_{44} & \mathbf{0} \\ \mathbf{A}_{51} & \mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{A}_{55} \\ \end{array} \right]$$

现在，想用最少的填充计算这个块矩阵的 LU 分解。

我通常知道用于减少一般稀疏矩阵填充的算法。说，Matlab 参考概述了几种方法及其对 Cholesky 分解的影响。然而，这些算法肯定不会给出最优的重新排序来为保持零的分解给出最优的结构。这样做有一个很好的理由：对于一个大的稀疏矩阵，找到一个最佳的重新排序是非常昂贵的、不需要的，并且与常见的相对快速的技术相比不太可能带来实质性的好处。

但是，我想知道对于块矩阵的分解是否会略有不同。在这种情况下，$N$小了一个数量级，人们可能愿意使用非常昂贵的 [graph?] 算法来找到给定块模式的最佳填充。

我想知道：

• 我应该看什么系列的算法？
• 是否有关于减少填充这方面的规范参考？（我的搜索经常被减少填充简单稀疏矩阵的结果所淹没，而不是具有其自身特点的分块情况——因为更昂贵的算法可能变得可行）？
• 对于相对较小的$N$来说，这甚至是一个明显的问题吗？

笔记：

• 在这个例子中，为简单起见，所有块都具有相同的$n \times n$大小，我对此很感兴趣。我可能对每个块仍然是正方形的示例感兴趣，但块大小不同。
• 对于我的应用程序，块数$N$的范围可以从 1（微不足道）到例如 100，并且$n$大约为数千（这根本$n$）。
• 我愿意花费大量的预计算时间（比如 10 $\times t_\text{LU}$）来分析模式并提出最佳重新排序