我有一个非常大的矩阵,为 n! x n! ,需要求出其行列式。对于 n 的每个排列,我将以下内容关联到:
- 长度为 2n 的向量(这在计算上很容易)
- 在 2n 个变量中的多项式(由 n 递归计算线性因子的积)
该矩阵是在点处进行多项式评估的矩阵,请将它们视为点。因此,矩阵的 sigma,tau 条目(由排列索引)是 tau 上的多项式在 sigma 处评估的结果。
例如: 对于 n=3
,如果第 i
个多项式是 (x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1)
,而第 j
个点是 (2,2,1,3,5,2)
,则该矩阵的第 (i,j)
个条目将是 (2 - 4)(1 - 5)(3 - 4)(2 - 1) = -8
。这里的 n=3
,因此这些点在 R^(3!) = R^6
中,而多项式有 3!=6
个变量。
我的目标是确定该矩阵是否非奇异。
我现在的方法是:
- 函数
point
接受一个排列并输出一个向量 - 函数
poly
接受一个排列并输出一个多项式 - 函数
nextPerm
给出按词典顺序的下一个排列
我代码的简略伪代码版本如下:
B := [];
P := [];
w := [1,2,...,n];
while w <> NULL do
B := B append poly(w);
P := P append point(w);
w := nextPerm(w);
od;
// BUILD A MATRIX IN MAPLE
M := Matrix(n!, (i,j) -> eval(B[i],P[j]));
// COMPUTE DETERMINANT IN MAPLE
det := LinearAlgebra[Determinant]( M );
// TELL ME IF IT'S NONSINGULAR
if det = 0 then return false;
else return true; fi;
我正在使用Maple中内置的函数
LinearAlgebra[Determinant]
,但其他所有函数都是使用低级Maple函数(例如seq
、convert
和cat
)构建的自定义函数。我的问题是这需要太长时间,意味着我可以耐心地处理
n=7
,但要得到n=8
需要数日。理想情况下,我希望能够达到n=10
。有人有办法可以改进吗?我可以尝试在不同的语言,比如Matlab或C中工作,但更希望找到一种在Maple中加速的方法。
我意识到这可能很难回答,因为每个函数的代码(例如
point
和poly
)已经进行了优化,因此真正的问题在于是否有一种更快的方式通过即时构建矩阵来计算行列式,或者类似的方法。更新:以下是我尝试过但不起作用的两个想法:
1. 我可以将多项式(因为它们需要一段时间才能计算出来,所以不想重新计算)存储到长度为
n!
的向量中,并即时计算点,并将这些值插入行列式的排列公式中。这里的问题是这是大小为矩阵O(N!)
,所以对于我的情况,这将是O((n!)!)
。 当n=10
时,(n!)!= 3,628,800!
,这实在太大了,甚至无法考虑。2. 使用LU分解计算行列式。幸运的是,我的矩阵主对角线上的元素都不为零,因此这是可行的。由于它的复杂度为矩阵大小的
O(N^3)
,因此这变成了O((n!)^3)
,这更接近可行。问题在于它需要我存储整个矩阵,这会对内存造成严重压力,更不用说运行时间了。因此,这也不起作用,至少没有一些更聪明的方式。有什么想法吗?