scipy.linalg.solve (LAPACK gesv) 在大矩阵上的时间复杂度? [英] Time complexity of scipy.linalg.solve (LAPACK gesv) on large matrix?

问题描述

如果我使用 scipy.linalg.在我的工作站上解决一个 ~12000 未知问题(具有 ~12000 平方、密集、非对称矩阵)(我认为它称为 LAPACK 的 gesv 函数)(我认为它称为 LAPACK 的 gesv 函数)，我在 <强烈>10-15 分钟.

只是为了探索可能的极限(注意我没有说有用")，我将我的潜在问题的分辨率提高了一倍，这导致需要解决大约 50000 个未知数.虽然从技术上讲，一旦我添加了更多 10 GB 的交换空间，这将在我的工作站上运行，但使用一些具有足够 RAM 的硬件似乎更为谨慎，因此我在 AWS EC2 高内存四重超大上启动了它... 过去 14 小时(嘿，Spot 实例很便宜)它一直在磨合的地方，而且无法判断它到底有多远.

Just to probe the limits of what's possible (note I don't say "useful"), I doubled the resolution of my underlying problem, which leads to needing to solve for ~50000 unknowns. While this would technically run on my workstation once I'd added some more 10s of GBytes of swap, it seemed more prudent to use some HW with adequate RAM, and so I kicked it off on an AWS EC2 High-Memory Quadruple Extra Large... where it has been grinding away for the last 14 hours (hey, spot instances are cheap) and it's impossible to tell how far through it is.

不幸的是，我不知道所涉及的求解器的时间复杂度是多少(我的 google-fu 在这个问题上失败了).如果是 O(N^2) 那么我预计它会在大约 4 小时后完成；如果是 O(N^3) 那么它可能会在 16 小时内完成.当然，这将 N 解释为未知数的数量 - 已经翻了四倍 - 矩阵中的元素数量增加了 16 倍！

Unfortunately, I've no idea what the time complexity of the solvers involved is (my google-fu failed me on this one). If it's O(N^2) then I'd have expected it to be done after around 4 hours; if it's O(N^3) then maybe it'll be done in 16 hours. Of course that's interpreting N as the number of unknowns - which has quadrupled - the number of elements in the matrix has increased by a factor of 16!

以及帮助我​​确定这是否有机会在我(项目的)有生之年完成或不感激收到的建议！

And advice which will help me determine whether this has any chance of completing in my (project's) lifetime or not gratefully received!

其他信息:

这里对稀疏矩阵不感兴趣(我的矩阵是密集的，无论如何，即使在 64 位上，scipy 也不能处理超过 2**31 个非零元素).

Sparse matrices aren't of interest here (my matrix is dense, and in any case scipy's don't work with more than 2**31 non-zero elements even on 64-bit).

我在工作站上使用 Debian/Squeeze 的 scipy，在 EC2 上使用 Ubuntu 12.04.显然都是 64 位.

I'm using Debian/Squeeze's scipy on the workstation, Ubuntu 12.04 on EC2. Both 64-bit obviously.

推荐答案

DGESV 对于 NxN 矩阵的时间复杂度为 O(N^3).请参见此处的表 3.13:http://www.netlib.org/lapack/lug/node71.html

The time complexity of DGESV for an NxN matrix is O(N^3). See Table 3.13 here: http://www.netlib.org/lapack/lug/node71.html

这篇关于scipy.linalg.solve (LAPACK gesv) 在大矩阵上的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！