线性系统的稀疏模式对于迭代 (KSP) 求解器是否重要?

计算科学 线性代数 宠物 迭代法
2021-12-24 11:17:16

差不多就是这个问题。给定一个一般的稀疏、非对称(数值和结构)矩阵,迭代求解器的稀疏模式(即矩阵/向量的行/列排列)有多重要?我可以看到通过直接影响填充的数量,它对于直接求解器 (LU) 或预处理器 (ILU) 变得很重要。

然而,对于迭代求解器,似乎最重要的部分是 MatVec 操作,它似乎并不关心实际的矩阵模式。是否有一些组件可能取决于我在这里没有考虑的模式?

并行怎么样?我怀疑该模式可能会在矩阵和向量的分布方式中变得重要,从而决定通信量/开销,但希望看到其他想法和输入。

我在一般情况下和关于 PETSc 的 KSP 求解器都问这个问题。

1个回答

排序仅在负载平衡/通信和预处理的适用性方面很重要。Krylov 方法不关心顺序,甚至不关心矩阵条目是否被存储。

在实践中,与矩阵相乘时,错误的排序可能需要比其他方式更多的通信。有关示例,请参阅 PETSc 用户手册中有关“自然排序”与“PETSc 排序”的部分。此外,与错误的并行分区相对应的排序可能会降低域分解预处理器的效率。请注意,这里重要的是分区,尽管分区会引发(等价类)排序。