符号行列式计算速度慢

Question

我正在做的一些研究需要象征性地取大矩阵的行列式；矩阵的范围从18x18到318x318。矩阵项在同一个变量omega中是数值或二次多项式。在

目前，我正在尝试在SymPy中使用.det()方法，但是它非常慢；一个18x18矩阵已经运行了45分钟以上，并且在我编写本文时仍在计算。我知道行列式计算是非常密集的，但是有什么我能做的来加速吗？ 我已经在Speeding up computation of symbolic determinant in SymPy上读过这篇文章，但是没有从文章中得到任何关于如何加快进程的建议。我能做什么？在

Answer 1

SymPy对行列式并不幼稚（参见MatrixDeterminant class），但似乎在整个计算过程中改变符号表达式是一个缓慢的过程。当行列式已知是一定次数的多项式时（因为矩阵项是），计算变量的多个值的数值并进行插值会更快。在

我的测试用例是一个密集的15×15矩阵，其中充满了变量omega的二次多项式，系数为整数。对于数值行列式，我仍然使用SymPy的.det方法，因此不管怎样，系数最终都是完全相同的长整数。在

import numpy as np
from sympy import *
import time
n = 15
omega = Symbol('omega')
A = Matrix(np.random.randint(low=0, high=20, size=(n, n)) + omega*np.random.randint(low=0, high=20, size=(n, n)) + omega**2 * np.random.randint(low=0, high=20, size=(n, n)))
start = time.time()
p1 = A.det()       # direct computation 
print('Time: ' + str(time.time() - start))

start = time.time()
xarr = range(-n, n+1)    # 2*n+1 points to get a polynomial of degree 2*n
yarr = [A.subs(omega, x).det() for x in xarr]  # numeric values
p2 = expand(interpolating_poly(len(xarr), omega, xarr, yarr))  # interpolation
print('Time: ' + str(time.time() - start))

p1和p2都是同一个多项式。运行时间（在相当慢的机器上，来自亚马逊的t2.nano）：

• 直接计算74.6秒
• 插值时间为5.4秒。在

如果您的系数是浮点数，并且在处理它们时不希望得到精确的算术结果，则可以通过将矩阵计算为NumPy数组并使用NumPy方法来实现进一步的加速：

^{pr2}$