计算科学 - 求解可以重新排序为块对角线形式的稀疏矩阵系统 - 吾爱随笔录

求解可以重新排序为块对角线形式的稀疏矩阵系统

计算科学线性代数稀疏矩阵块分解

2021-11-30 23:36:45

我有一类由域分解方法创建每个矩阵代表几个大小相等的子问题，我知道对于某些置换矩阵，将是一个块对角系统，即解决这个系统的某个右手边显然只是反转每个块并重新排列回原来的顺序的问题。问题是当将系统置换为块对角形式所需的顺序未知时，是否有任何方法用于此类系统。 $A$ $P$ $PAP^T$

A = [\begin{matrix} A_{1} & 0 & 0 \\ 0 & A_{2} & 0 \\ 0 & 0 & A_{3} \end{matrix}]

$A = \begin{bmatrix} A_1 & 0 & 0 \\ 0 & A_2 & 0 \\ 0 & 0 & A_3 \\ \end{bmatrix}$

一种方法是将矩阵系统解释为图形，并尝试找到循环。然后可以根据每个循环通过排序来排列系统。那么问题是哪些算法快速且适合该目的？
这种系统的条件数通常比块连接的类似系统的条件数低得多，因为特征值是每个子块的特征值。一个普遍感兴趣的问题可能是哪些算法擅长在不实际置换系统的情况下解决此类系统 - 由于条件数降低，对于更解耦的系统，CG 可能会收敛得更快。对于这类问题，一些算法是否更好？
这种系统有已知的命名法吗？在搜索块对角矩阵的反转/排列时，我通常会发现除了最后一行之外的块对角系统 - 确实是一个不同的问题。

虽然我解决每个系统都没有问题，但我认为这个问题很有趣。就矩阵性质而言，子矩阵可以被认为类似于热方程的五点模板——它们来自类似的质量守恒系统。（我希望这是大家普遍感兴趣的，所以关注子矩阵的结构不是很重要）

2个回答

Q1要找到矩阵中的各个块（并因此恢复块排列），您可以在底层图中找到连接的组件。这可以通过从未访问的顶点重复广度优先搜索来有效地完成（O(|E|)对于带有边的图）：E

for (i = all vertices in graph G)
    if (vertex i is unvisited)
        // start a BFS from vertex i
        // all of the vertices visited during this BFS will be 
        // part of the same diagonal block
    endif
endfor

请注意，这仅标识矩阵中的块结构 - 仍然存在可以在每个块内本地应用的整个排列系列。根据您选择的线性求解器，您可以选择适当的排序方案（AMD、RCM等）。

Q2我不明白你在这里得到什么 - 因为对角线块彼此完全解耦我不明白你为什么不单独解决它们 - 如果你对速度感兴趣，可以并行解决。

Q3块对角线是正确的名称 - 据我所知。

在 Q1：在 FEM/FDM 语言中，您将应用 Cuthill-McKee 算法对所有相互连接的自由度进行编号。一旦算法在没有对所有自由度进行编号的情况下停止，您就知道矩阵还有另一个尚未编号的组件，您将继续使用它的一个自由度，使用下一个可用索引。这样，您就得到了矩阵的块对角结构——换句话说，Cuthill-McKee 算法将为您计算排列。

关于 Q2：只要您有一个不变的预条件子，所有 Krylov 空间方法都具有独立于自由度编号的收敛特性（即，它们在排列下是不变的）。

其它你可能感兴趣的问题

上一篇计算永久物64 × 6464×64矩阵下一篇具有静态维度的“特征”矩阵