如果我使用 scipy.linalg.solve (我认为这称为 LAPACK 的 gesv 函数)在我工作站上的一个 ~12000 未知问题(具有 ~12000 平方、密集、非对称矩阵)上，我在 中得到了一个很好的答案。 10-15 分钟 .
只是为了探索可能的极限(请注意，我没有说“有用”)，我将潜在问题的分辨率提高了一倍，这导致需要解决大约 50000 个未知数。虽然从技术上讲，一旦我添加了更多 10 GB 的交换空间，这将在我的工作站上运行，但使用一些具有足够 RAM 的硬件似乎更为谨慎，因此我在 AWS EC2 高内存四重超大上启动了它。 .. 上一次它一直在磨削的地方 14小时 (嘿，Spot 实例很便宜)而且无法确定它有多远。
不幸的是，我不知道所涉及的求解器的时间复杂度是多少(我的 google-fu 在这个问题上失败了)。如果是 O(N^2) 那么我预计它会在大约 4 小时后完成；如果它是 O(N^3) 那么它可能会在 16 小时内完成。当然，这将 N 解释为未知数的数量——它已经翻了四倍——矩阵中的元素数量增加了 16 倍!
以及将帮助我确定这是否有机会在我(项目的)一生中完成或不感激收到的建议!
其他信息:
这里对稀疏矩阵不感兴趣(我的矩阵是密集的，无论如何，即使在 64 位上，scipy 也不能处理超过 2**31 的非零元素)。
我在工作站上使用 Debian/Squeeze 的 scipy，在 EC2 上使用 Ubuntu 12.04。显然都是64位的。
最佳答案
NxN 矩阵的 DGESV 时间复杂度为 O(N^3)。请参阅此处的表 3.13:
http://www.netlib.org/lapack/lug/node71.html
关于performance - scipy.linalg.solve (LAPACK gesv) 在大矩阵上的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12660052/