由于求解线性系统的直接消除方法的计算复杂度为，因此在自由度数较大时不实用。但是你会称它为多大的系统呢？我看到一些材料说，当你应该考虑迭代方法时，100,000 自由度将是分水岭。不会太大了吧？我的意思是当自由度达到不到 100,000 时，使用直接方法的复杂度将是，很难想象我们能够承受如此巨大的复杂度？当直接消除方法被视为不切实际时，谁能给出一些具体的例子或直观的建议来指示通常的上限？文学作品也不错。谢谢！
关于线性系统直接求解器的不切实际使用
计算科学
线性求解器
迭代法
复杂
2021-12-19 19:24:02
1个回答
“100,000 个未知数”的经验法则适用于稀疏矩阵而不是密集矩阵。一个根本不利用稀疏性的简单直接求解器原则上可能对某些矩阵具有复杂度。在实践中，一个好的直接求解器的计算复杂度要低得多。
一个更好的起点是查看带状矩阵。分解带宽为的矩阵需要时间，并且这些因子也具有带宽。如果您可以重新排序稀疏矩阵以使其具有较小的带宽，那么您可以使直接因式分解更易于管理。不幸的是，计算最佳重新排序是 NP 完全的。幸运的是，有一些很好的启发式方法，即Cuthill-McKee 算法，可以减少图的带宽。
现在大多数 FEM 矩阵，尤其是 3D 矩阵，实际上具有相当高的带宽。与其采取这种通过减少带宽来减少填充的间接方法，不如询问在可能性，为直接矩阵分解提供最少的填充。这个问题也是 NP 完全的，但也有一些很好的启发式方法。这些启发式方法是近似最小度数排序的基础。一个很好的参考是Amestoy关于 AMD 订购的原始论文和Tim Davis 的书。
正如比尔格林建议的那样，您也应该自己尝试一下。scipy有一个稀疏的 LU 分解例程，您可以在其中指定保持矩阵的自然顺序，或使用 AMD。您可以随时在SuiteSparse 矩阵集合上尝试一下。