有效的方法来决定一个n的决定因素!XN!Maple中的矩阵

Question

我有一个大矩阵,n!xn !,我需要采取决定因素.对于n的每个排列,我都联想到了

• 一个长度为2n的向量(这很容易计算)
• 2n个变量的多项式(在n上递归计算的线性因子的乘积)

矩阵是向量处的多项式的评估矩阵(被认为是点).因此,矩阵的sigma,tau入口(由置换索引)是在tau的向量处评估的sigma的多项式.

示例:对于n=3,如果第ith个多项式是(x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1)并且第jth个是(2,2,1,3,5,2),那么(i,j)矩阵的第th个条目将是(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)更接近可行.但问题是,它需要我存储整个矩阵,这会对内存造成严重压力,无需考虑运行时间.所以这也不起作用,至少不是没有更多的聪明.有任何想法吗？

Answer 1

不确定我是否遵循了你的问题；是（或者减少为）以下内容吗？

您有两个由 n 个数字组成的向量，将它们称为x和c，然后矩阵元素是k的乘积(x_k+c_k)，每行/列对应于x和的不同顺序c？

x如果是这样，那么我相信只要或中存在重复值，矩阵就会是奇异的c，因为矩阵将具有重复的行/列。n在较小的具有不同值的上尝试一系列蒙特卡洛方法x，c看看这种情况是否总体上是非奇异的 - 如果对于 6 来说是这样，那么对于 10 来说很可能也是如此。

就暴力破解而言，您的方法是：

1. 是一个无用的人
2. 工作速度会更快（对于 应该是几秒钟n=7），尽管您可能想尝试 SVD 而不是 LU，这会更好地让您知道矩阵的表现如何。