时间scipy.linalg.solve（LAPACK gesv）对大型矩阵的复杂性？ [英] Time complexity of scipy.linalg.solve (LAPACK gesv) on large matrix?
问题描述
如果我使用 SciPy的.linalg.solve 我的工作站上（我相信调用LAPACK的gesv功能）上〜12000未知的问题（有〜12000平方，致密，非对称矩阵），我得到一个很好的答案 10-15分钟
只是为了探索什么是可能的限制（请注意，我不说有用），我一倍我根本问题，从而导致需要解决的〜50000未知的分辨率。虽然我的工作站上，这将在技术上运行一次我会添加掉GB的一些10S，它显得比较谨慎地使用一些硬件有足够的RAM，所以我在一个AWS EC2高内存四超大踢它关闭。 ..它已被磨走过去14小时（嘿，现货实例是便宜），它是不可能告诉多远通过它。
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.
不幸的是，我不知道是什么所涉及的解算器的时间复杂度为（我的谷歌福失败了我在这件）。如果是O（N ^ 2），那么我会想到是后大约4小时内完成;如果是O（N ^ 3），那么也许它会在16小时内完成。当然，这是除preting 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!
其它信息：
稀疏矩阵是不是这里的利益（我的矩阵密，并且在任何情况下SciPy的的不超过 2 ** 31 非零元素工作即使在64位）。
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 /挤压的SciPy的，Ubuntu的12.04 EC2上。 64位明显。
I'm using Debian/Squeeze's scipy on the workstation, Ubuntu 12.04 on EC2. Both 64-bit obviously.
推荐答案
DGESV的的N×N矩阵的时间复杂度为O（N ^ 3）。见表3.13的位置： <一href="http://www.netlib.org/lapack/lug/node71.html">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屋！
