Skip to main content
 首页 » 编程设计

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

2025年04月02日14qq号

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

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

对于 3x3,执行此代码需要大约 0.8 秒,对于 6x6,执行此代码需要大约 288 秒(det 函数仅需 650 毫秒,其余用于 Poly)。对于 10x10,要么复杂性以惊人的速度增加,要么其他一些原因阻止它从 Poly 调用返回(我等了一个星期)。不会抛出任何异常。

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

我在 0.7.1 上,刚刚升级到 1.0(两个版本都有问题)。

我添加了日志记录以尝试获取文件的行列式,但它再次出现在 str(deter) 函数调用中。如果我破坏了我的调试器无法显示威慑(对于调试器来说可能太大了)。

这是一个堆栈:

MainThread - pid_135368_id_42197520  
  _print [printer.py:262]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  parenthesize [str.py:29]   
  _print_Mul [str.py:290]    
  _print [printer.py:257]    
  _print_Add [str.py:56]     
  _print [printer.py:257]    
  doprint [printer.py:233]   
  sstr [str.py:748]  
  __str__ [basic.py:396]     
  _getRoots_sympy_Poly_nroots [__init__.py:91]   
  getRoots [__init__.py:68]  
  findPolyRoots [__init__.py:697]    
  _getNroots [polefinder.py:97]  
  _doForN [polefinder.py:60]     
  _incN [polefinder.py:52]   
  __init__ [polefinder.py:39]    
  _doPoleFind [polefinderwrap.py:33]     
  _polesForPos [polefinderwrap.py:47]    
  <module> [polefinderwrap.py:60]    
  run [pydevd.py:937]    
  <module> [pydevd.py:1530]  

好的,我从 str 函数中得到了一个异常。似乎多项式变得太大了。

Traceback (most recent call last): 
  File "E:\Peter's Documents\PhD\Code\Git\ProtoQScat\multichannel\qscat\ratsmat.\polefinder.py", line 60, in _doForN 
    roots = self._getNroots(N) 
  File "E:\Peter's Documents\PhD\Code\Git\ProtoQScat\multichannel\qscat\ratsmat.\polefinder.py", line 97, in _getNroots 
    roots = ratSmat.findPolyRoots(False) 
  File "E:\Peter's Documents\PhD\Code\Git\ProtoQScat\multichannel\qscat\numerical/..\ratsmat\__init__.py", line 697, in findPolyRoots 
    roots = self.polyRootSolve.getRoots(mat, k) 
  File "E:\Peter's Documents\PhD\Code\Git\ProtoQScat\multichannel\qscat\numerical/..\ratsmat\__init__.py", line 68, in getRoots 
    ret = self._getRoots_sympy_Poly_nroots(mat, k) 
  File "E:\Peter's Documents\PhD\Code\Git\ProtoQScat\multichannel\qscat\numerical/..\ratsmat\__init__.py", line 91, in _getRoots_sympy_Poly_nroots 
    self.resultFileHandler.writeLogStr(str(deter)) 
  File "C:\Python27\lib\site-packages\sympy\core\basic.py", line 396, in __str__ 
    return sstr(self, order=None) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 748, in sstr 
    s = p.doprint(expr) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 233, in doprint 
    return self._str(self._print(expr)) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 257, in _print 
    return getattr(self, printmethod)(expr, *args, **kwargs) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 56, in _print_Add 
    t = self._print(term) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 257, in _print 
    return getattr(self, printmethod)(expr, *args, **kwargs) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 290, in _print_Mul 
    a_str = [self.parenthesize(x, prec) for x in a] 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 29, in parenthesize 
    return "(%s)" % self._print(item) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 257, in _print 
    return getattr(self, printmethod)(expr, *args, **kwargs) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 56, in _print_Add 
    t = self._print(term) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 257, in _print 
    return getattr(self, printmethod)(expr, *args, **kwargs) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 290, in _print_Mul 
    a_str = [self.parenthesize(x, prec) for x in a] 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 29, in parenthesize 
    return "(%s)" % self._print(item) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 257, in _print 
    return getattr(self, printmethod)(expr, *args, **kwargs) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 56, in _print_Add 
    t = self._print(term) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 257, in _print 
    return getattr(self, printmethod)(expr, *args, **kwargs) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 290, in _print_Mul 
    a_str = [self.parenthesize(x, prec) for x in a] 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 29, in parenthesize 
    return "(%s)" % self._print(item) 
  File "C:\Python27\lib\site-packages\sympy\printing\printer.py", line 257, in _print 
    return getattr(self, printmethod)(expr, *args, **kwargs) 
  File "C:\Python27\lib\site-packages\sympy\printing\str.py", line 69, in _print_Add 
    return sign + ' '.join(l) 
MemoryError 

编辑: 根据下面的答案,这里是一个具有行列式大小( channel )的剖面图。忽略 N(在 y 轴上)它是计算的另一个参数(控制元素中多边形的大小)。

请您参考如下方法:

算法很慢。

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 .

该算法对于高度并行化的架构来说速度很快;它的主要动机是高斯消除法不能很好地并行化。正式地,它在 class NC^2 中.我可能猜想您的测试没有在这样的架构上运行。一些研究人员进入算法seem to be contributors on CS.SE ,如果您对该主题有更多问题。

多项式调用很慢

From the docs ,有多种构造多项式的方法,具体取决于传递给构造函数的集合类型(列表 [1]、元组 [2] 或字典 [3]);它们导致不同的验证并具有非常不同的性能。我会向您指出该文档中的这个注释(强调我的,大写他们的):

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 还保留延迟计算表达式直到需要其输出的权利。这是符号计算优势的重要组成部分 - 数学简化可以提高精度和性能,但这也可能意味着复杂表达式的实际计算可能会延迟到意想不到的时间。