我目前正在解决由某些算法生成的非常大的对称（但不是正定）系统。这些矩阵具有很好的块稀疏性，可用于并行求解。但我无法决定是否应该使用直接方法（如多正面）或迭代方法（预处理 GMRES 或 MINRES）。我所有的研究表明，迭代求解器（即使 7 次内部迭代的收敛速度非常快）无法击败 MATLAB 中的直接 '\' 运算符。但理论上，直接方法应该更昂贵。这是怎么回事？这种情况下是否有最新的文件或文件？我能否在使用直接方法的并行系统中像 GMRES 这样灵活的迭代求解器一样高效地使用块稀疏性？
大型稀疏对称（但不是正定）系统的最佳求解器选择
计算科学
并行计算
线性求解器
稀疏矩阵
线性系统
格瑞斯
2021-12-05 04:56:45
4个回答
MUMPS 稀疏直接求解器可以处理对称不定系统并且可以免费获得 ( http://graal.ens-lyon.fr/MUMPS/ )。Ian Duff 是 MUMPS 和 MA57 的作者之一，因此这些算法有很多相似之处。
MUMPS 是为分布式内存并行计算机设计的，但它也适用于单处理器机器。如果将它与多线程 BLAS 库链接，则可以在共享内存、多核处理器上实现合理的加速。
您没有说“非常大”有多大，但 MUMPS 还具有核外功能来处理因式矩阵不适合可用内存的问题。
直接求解器遇到的一般问题是填充现象，这意味着稀疏矩阵的逆矩阵可能是密集的。如果矩阵的结构不“合适”，这会导致巨大的内存需求。
有一些尝试解决这些问题，MATLAB 的默认lu-function 使用了其中的一些。有关排列、对角缩放等的概述，请参见http://www.mathworks.de/de/help/matlab/ref/lu.html 。当然，对于像 MUMPS（http://graal.ens-lyon.fr/MUMPS/）这样的更高级的软件包也是如此。
但是，一般来说，如果您的问题足够大，您将达到内存边界，并且您将不得不使用迭代 (Krylov) 方法。
如果您的问题是对称且不确定的，那么 MINRES 可能是显而易见的选择。但是请注意，它可能会在底层 Arnoldi 过程中失去正交性。GMRES 可以在这里提供帮助。在精确的算术中，它与 MINRES 做同样的事情，但倾向于更好地处理正交性问题。这是以比 MINRS 更高的内存要求为代价的。有人认为 GMRES 是“MINRES 的最佳实施”。
在任何情况下，您都可能会从对系统进行预处理中获益。如果您不想花时间定制预处理器，不完整的 LU 分解预处理器 (ILU) 可能已经让您有所收获。
任何迭代求解器只有在问题足够大时才能胜过直接方法（大，取决于几个因素，例如所需的存储空间、实施效率）。而且，任何 krylov 方法（例如 GMRES）只有在您使用适当的预处理（在实践中）时才有效。如果您不使用任何预处理，则 krylov 方法通常没有用。我也使用块稀疏矩阵（这些来自 PDE 应用程序）并观察到块预处理（重叠加性 schwarz）krylov 求解器（重新启动的 GMRES 或 BiCG-Stab）加上粗网格校正（或多重网格）对于这些是可扩展的矩阵类型。
由于一流的编程，Matlab '\' 运算符非常高效。您可能会在 Timothy Davis 的书中看到一些想法以及他们如何使用所有可能的捷径。
在 matlab 中，您可以使用 gmres，它开发良好且稳定。可能 minres 理论上应该适合您的情况，但可能并不那么可靠（至少我的经验是这样的）。您应该从 matlab gmres 获得相同或更高的效率，如果
- 您的系统足够大（至少几千乘几千）。
- 如果您使用正确的参数类型（RESTART、MAXIT、X0）。对此没有明确的指导方针。使用你的经验。
- 使用好的预处理器。您可以使用 ILU 甚至更便宜的块 Jacobi。这将大大减少工作量。
- 最重要的：如果您的矩阵是稀疏的，请使用 matlab 稀疏格式。Matlab gmres 就是为此而构建的。这将在很大程度上降低成本。
对于更大的系统，请使用 PETSc 之类的工具。