algorithm - 高效求解稀疏矩阵

Question

为了解决备用矩阵，

一般来说，矩阵必须有多大（根据经验）

对于像 congraduate 下降这样的方法比蛮力求解器（不利用稀疏性）更快？

Answer 1

它不仅取决于矩阵的大小，还取决于它们的稀疏程度以及它们具有的稀疏结构。显然，您可以比在矩阵中随机分布相同数量的非零条目的系统更快地求解三对角系统。

正如 High-Performance Mark 所指出的，CG 既适用于密集矩阵，也适用于稀疏矩阵，因此您要问的问题更像是“矩阵需要多大和多稀疏才能使求解器受益于处理它作为稀疏矩阵而不是恰好有很多零的密集矩阵”。

正如我所指出的，这个问题的答案取决于稀疏结构。一个没有特殊结构且 10% 已满的矩阵，作为第一个猜测，我会使用密集方法，直到矩阵填充缓存（在现代商品硬件上，这将是 1000 x 1000 左右）。如果矩阵非常稀疏，或者具有一些使其更易于使用的特殊结构（例如，密集的非零数据块或一些带结构），那么该阈值将变得更小。

您能否向我们提供有关您正在处理的具体问题的更多信息？

Answer 2

我不确定您在共轭梯度求解器和“蛮力”求解器之间的二分法是否有用。例如，CG 可以应用于密集矩阵和稀疏矩阵。你可能会发现这本书很有帮助。