首页 文章

如何计算scipy稀疏矩阵行列式而不将其变为密集？

提问于
浏览 次
22

我试图找出在python中找到稀疏对称和实矩阵行列式的最快方法 . 使用scipy sparse 模块，但真的很惊讶没有行列式功能 . 我知道我可以使用LU分解来计算行列式，但是没有看到一个简单的方法来执行它，因为 scipy.sparse.linalg.splu 的返回是一个对象并且实例化一个密集的L和U矩阵是不值得的 - 我不妨做 sp.linalg.det(A.todense()) where A 是我的scipy稀疏矩阵 .

我也有点惊讶为什么其他人没有面对scipy中有效决定因素计算的问题 . 如何使用 splu 来计算行列式？

我查看了 pySparse 和 scikits.sparse.chlmod . 后者对我来说现在不实用 - 需要软件包安装，也不确定在我遇到麻烦之前代码的速度有多快 . 有解决方案吗提前致谢 .

python numpy scipy linear-algebra sparse-matrix

2 回答

  • 4

    以下是我作为答案的一部分提供的一些参考资料here . 我认为它们解决了您要解决的实际问题：

    • notes用于Shogun图书馆的实施

    • Erlend Aune，Daniel P. Simpson：高维高斯分布中的参数估计，特别是第2.1节（arxiv:1105.5256）

    • Ilse C.F. Ipsen，Dean J. Lee：行列式近似（arxiv:1105.0437）

    • Arnold Reusken：大稀疏对称正定矩阵行列式的逼近（arxiv:hep-lat/0008007）

    引自幕府将军的笔记：

    在似然表达式中计算对数行列式项的常用技术依赖于矩阵的Cholesky分解，即Σ= LLT，（L是下三角Cholesky因子），然后使用因子的对角项来计算log（ DET（Σ））=2Σni= 1log（LII） . 然而，对于稀疏矩阵，由于协方差矩阵通常是，Cholesky因子经常遭受填充现象 - 它们本身并不那么稀疏 . 因此，对于大尺寸，由于存储所有这些不相关的因子非对角系数的大量存储器需求，该技术变得不可行 . 虽然已经开发了订购技术以预先对行和列进行置换以便减少填充，例如，近似最小度（AMD）重新排序，这些技术在很大程度上取决于稀疏性模式，因此无法保证提供更好的结果 . 最近的研究表明，使用复杂分析，数值线性代数和贪婪图着色等多种技术，我们可以将对数行列式逼近任意精度[Aune et . al . ，2012] . 主要技巧在于我们可以将log（det（Σ））写为trace（log（Σ）），其中log（Σ）是矩阵对数 .

    回复于
  • 5

    解决这个问题的“标准”方法是使用cholesky分解，但是如果你不能使用任何新的编译代码，那么你就不走运了 . 最好的稀疏cholesky实现是蒂姆戴维斯的CHOLMOD，它是根据LGPL许可的，因此不适用于scipy本身（scipy是BSD） .

    回复于

相关问题