6

我有一个大矩阵，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)更接近可行。但是，问题在于它需要我存储整个矩阵，这对内存造成了严重压力，更不用说运行时间了。所以这也行不通，至少在没有一点聪明的情况下是行不通的。有任何想法吗？

4

2 回答 2

2

我不清楚你的问题是空间还是时间。显然，两者来回交易。如果您只想知道行列式是否为正，那么您绝对应该进行LU分解。原因是如果A = LU有L下三角和U上三角，那么

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

所以您只需要确定 or 的任何主对角线条目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;
  }
}

关键是您可以同时计算第ith 行U和第ith 列L，并且您只需要知道上一行/列即可继续前进。通过这种方式，您可以尽可能多地并行处理并尽可能少地存储。由于您可以根据需要计算条目a_ij，因此这需要您存储两个长度向量，n同时生成另外两个长度向量n（ 的行U、 的列L）。该算法需要n^2时间。您也许可以找到更多技巧，但这取决于您的空间/时间权衡。

于 2013-03-05T04:27:40.090 回答
-1

不确定我是否关注了您的问题；是（或减少到）以下？

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

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

就蛮力而言，您的方法：

  1. 是非首发
  2. 将更快地工作（应该是几秒钟n=7），尽管您可能想尝试 SVD 而不是 LU，这将更好地让您知道矩阵的表现如何。
于 2013-02-24T09:27:32.497 回答