在Maple中高效地计算n！x n！矩阵行列式的方法

Question

我有一个非常大的矩阵，为 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），这更接近可行。问题在于它需要我存储整个矩阵，这会对内存造成严重压力，更不用说运行时间了。因此，这也不起作用，至少没有一些更聪明的方式。有什么想法吗？

- Daniel

---

你的多项式系数和评估点来自哪个域？你的例子中显示为整数 - 这是简化了还是实际情况？ - Erik P.

Answer 1

我不确定你的问题是关于空间还是时间。显然，两者相互影响。如果你只想知道行列式是否为正数，那么你应该选择LU分解。原因是如果A = LU，其中L是下三角矩阵，U是上三角矩阵，那么

det(A) = det(L) det(U) = l_11 * ... * l_nn * u_11 * ... * u_nn

因此，您只需要确定L或U的任何主对角线条目是否为0。

为了进一步简化，使用Doolittle算法，其中l_ii = 1。如果在任何时候算法崩溃，则矩阵是奇异的，因此您可以停止。以下是要点：

for k := 1, 2, ..., n do {
  for j := k, k+1, ..., n do {
    u_kj := a_kj - sum_{s=1...k-1} l_ks u_sj;
  }
  for i = k+1, k+2, ..., n do {
    l_ik := (a_ik - sum_{s=1...k-1} l_is u_sk)/u_kk;
  }
}

关键在于您可以同时计算U的第i行和L的第i列，并且只需知道前一行/列即可向前移动。这样，您可以尽可能并行处理，并存储所需最少的内容。由于您可以按需计算条目a_ij，因此需要存储两个长度为n的向量，同时生成两个长度为n的向量（U的行和L的列）。该算法需要n^2的时间。您可能会发现更多技巧，但这取决于您的空间/时间权衡。

- PengOne

---

这看起来像是我必须存储两个LU矩阵才能计算它们。我的内存不足以支持这样做。有其他的方法吗？ - Daniel

Answer 2

不确定我是否理解了你的问题；它是以下内容吗（或者简化为以下内容）？

您有两个包含n个数字的向量，称之为x和c，则矩阵元素是针对(xk+ck)的k乘积，每行/列对应于x和c的不同排序？

如果是这样，那么我认为只要x或c中存在重复值，矩阵就会是奇异的，因为矩阵将具有重复的行/列。尝试在较小的n个具有不同x和c值的情况下进行一堆蒙特卡洛模拟，看看通常情况下是否非奇异-如果对6成立，则很可能对10成立。

至于暴力方法，您的方法：

1. 没有任何作用
2. 将会更快地运行（对于n=7应该只需要几秒钟），不过你可能想尝试SVD，它会更好地告诉你矩阵的行为如何。

- Jon

---

一个向量包含在R^(n!)中的点，例如(2,2,1,3,5,2)，另一个向量包含n!个变量的多项式，例如(x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1)。矩阵是在这些点上对多项式的求值，例如示例的条目将是(2 - 4)(1 - 5)(3 - 4)(2 - 1)。 - Daniel

蒙特卡罗方法对此毫无帮助。我有一组特定的点向量和一组特定的多项式向量，我需要知道这些多项式在这些点上的评估矩阵是否是非奇异的。至少就我所知，你不能用蒙特卡罗方法来解决这个问题。 - Daniel