我试图找出最快的方法来寻找稀疏对称矩阵和真实的矩阵的行列式在python中。使用scipy sparse
模块,但真的很惊讶,没有行列式函数。我知道我可以使用LU分解来计算行列式,但不'我看不出有什么简单的方法,因为scipy.sparse.linalg.splu
的返回是一个对象,示例化一个密集的L和U矩阵是不值得的-我也可以做sp.linalg.det(A.todense())
,其中A
是我的scipy稀疏矩阵。
我也有点惊讶为什么其他人没有在scipy中面对高效行列式计算的问题。一个人如何使用splu
来计算行列式呢?
我研究了pySparse
和scikits.sparse.chlmod
。后者现在对我来说并不实用-需要安装软件包,而且在我陷入所有麻烦之前也不确定代码有多快。有什么解决方案吗?提前感谢。
4条答案
按热度按时间niwlg2el1#
下面是我在回答here时提供的一些参考,我认为它们解决了您试图解决的实际问题:
引用幕府笔记:
计算似然表达式中的对数行列式项的常用技术依赖于矩阵的Cholesky因式分解,即Σ=LLT,(L是下三角Cholesky因子),然后使用该因子的对角项计算log(检测(Σ))=2∑ni= 1 log然而,对于稀疏矩阵,如协方差矩阵通常那样,Cholesky因子经常遭受填充现象-它们本身并不那么稀疏。因此,对于大的维数,由于需要大量的存储器来存储因子的所有这些不相关的非对角系数,所以该技术变得不可行。虽然已经开发了排序技术来预先置换行和列以减少填充,例如近似最小度(AMD)重新排序,但是这些技术很大程度上依赖于稀疏模式,因此不能保证给予更好的结果。
最近的研究表明,使用复分析、数值线性代数和贪婪图着色等技术,我们可以将对数行列式逼近到任意精度[Aune et. al.,2012]。主要技巧在于我们可以将log(det(Σ))写成trace(log(Σ)),其中log(Σ)是矩阵对数。
ogq8wdun2#
解决这个问题的“标准”方法是使用cholesky分解,但是如果您不准备使用任何新编译的代码,那么您就不走运了。最好的稀疏cholesky实现是Tim Davis的CHOLMOD,它是在LGPL下许可的,因此在scipy中不可用(scipy是BSD)。
mhd8tkvw3#
可以使用
scipy.sparse.linalg.splu
来获取M=LU
分解的下三角矩阵(L
)和上三角矩阵(U
)的稀疏矩阵:于是行列式
det(M)
可以表示为:三角矩阵的行列式就是对角项的乘积:
但是,对于large matrices underflow or overflow commonly occurs,可以通过使用对数来避免。
注意,我使用复数运算来计算对角线上可能出现的负数,现在,从
logdet
可以恢复行列式:而行列式的符号可以直接从
diagL
和diagU
计算(例如当实施Crisfield的弧长方法时是重要的):其中
swap_sign
是LU分解中考虑排列数目的一项,感谢@Luiz Felippe Rodrigues,它可以计算为:omtl5h9j4#
使用SuperLU和CHOLMOD时,N = 1e6附近稀疏三对角(-1 2 -1)的行列式开始出错...
行列式应为N +1。
这可能是计算U对角线乘积时的误差传播:
输出:
4999993.625461911
4999993.625461119
即使U的精度为10 - 13位,也可能出现以下情况:
4999993.749444371