在处理复杂的行列式时，Sympy永远不会返回

Question

至少它看起来是这样的。以下代码对于3x3和6x6矩阵的行为正确。

    deter = mat.det('method':'berkowitz')
    #self.resultFileHandler.writeLogStr(str(deter))
    a = sy_polys.Poly(deter, k)

对于3x3，执行此代码需要~0.8s，对于6x6则需要~288s（det函数只有650ms，其余为Poly）。对于10x10，要么复杂性以巨大的速度急剧上升，要么是其他原因阻止了它从Poly调用中返回（我等了一个星期）。不会引发异常。

行列式的元素由大的符号多项式组成。

我使用的是0.7.1，刚升级到1.0（两个版本都有问题）。

我添加了日志以尝试将行列式放入文件中，但它仍然停留在str（dester）函数调用中。如果我中断了，我的调试器就不能显示detrt（prob对于调试器来说太大了）。

这是一个堆栈：

^{pr2}$

好的，我有一个str函数的异常。似乎多项式变得太大了。

^{3}$

编辑： 下面的答案是用行列式大小（通道）绘制的剖面图。忽略N（在y轴上）这是计算的另一个参数（控制元素中多边形的大小）。

Answer 1

算法很慢。

Sympy解释了the Berkowitz method in its documentation，并引用了"On computing the determinant in small parallel time using a small number of processors"；实现了look at the open-source sympy code。在

Berkowitz的复杂性很难理解，如果你不想用暴力来证明它的正确性then you need to get involved in some pretty hairy combinatorics。在

对于高度Pararallized的体系结构，该算法的速度很快；它主要是因为高斯椭圆化没有很好地parralize。形式上，它在class ^{}中。我猜你的测试不是在这样的架构上运行的。如果你对这个主题有更多的问题，一些研究人员会对算法seem to be contributors on CS.SE感兴趣。在

多项式调用很慢

From the docs，有多种构造多项式的方法，这取决于传递给构造函数的集合的类型（列表[1]、元组[2]或字典{}）；它们导致不同的验证，并具有非常不同的性能。我要向你指出文件中的这一点（强调我的，大写他们的）：

For interactive usage choose [1] as it’s safe and relatively fast.

CAUTION: Use [2] or [3] internally for time critical algorithms, when you know that coefficients and monomials will be valid sympy expressions. Use them with caution! If the coefficients are integers instead of sympy integers (e.g. 1 instead of S(1)) the polynomial will be created but you may run into problems if you try to print the polynomial. If the monomials are not given as tuples of integers you will have problems.

---

Sympy还保留在需要表达式输出之前对表达式进行懒惰求值的权利。这是符号计算好处的一个重要部分——数学简化可以带来精度和性能的提高，但也可能意味着复杂表达式的实际计算可能会延迟到意想不到的时间。在

Answer 2

好的，所以我在阅读了文献之后，又回到了这个问题上（这里重点强调），伯克维茨应该在O（n^2）和O（n^3）之间运行。在

我发现det和Poly的输入类型对性能有很大的影响（我承认在我的问题中没有显示输入类型）。将原始表达式包装在多边形中可显著提高性能。在

考虑以下三个代码

1:使用矩阵符号。det耗时1.1s，30分钟后仍停留在str上

from sympy import MatrixSymbol, Matrix

X = MatrixSymbol('X', 10, 10)
Xmat = Matrix(X)

deter = Xmat.det(method='berkowitz')
str(deter)

2:表示我原来的问题代码。det花了1.8秒，30分钟后仍然停留在Poly上

^{pr2}$

3:以上，但带有m[i,j] = poly(。det取3.0s，Poly取0.04，nroots取0.27

import sympy
from sympy import Matrix, I
from sympy import poly
from sympy.polys import Poly

matSz = 10

m = Matrix([[0.0]*matSz]*matSz)

x = sympy.symbols('x')
for i in range(matSz):
  for j in range(matSz):
    m[i,j] = poly(2.0*float(i+1)*x**2 + 2.0*float(j+1)*x*I - 5.0*float(i+1))

deter = m.det(method='berkowitz')
deter_poly = Poly(deter, x)  #Required or exception
roots = deter_poly.nroots()