首页 文章

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

提问于
浏览 次
6

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

  • 长度为2n的向量（这很容易计算）

  • 在2n个变量中的多项式（在n上递归计算的线性因子的乘积）

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

Example ：对于 n=3 ，如果 i th多项式为 (x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1) 且 j th点为 (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;

我正在使用内置函数 LinearAlgebra[Determinant] 在Maple中工作，但其他一切都是使用低级Maple函数的自定义构建函数（例如 seq ， convert 和 cat ） .

我的问题是，这需要太长时间，这意味着我可以耐心等待，但获得 n=8 需要数天 . 理想情况下，我希望能够到达 n=10 .

有没有人知道如何改善时间？我愿意用不同的语言工作，例如Matlab或C，但更愿意找到一种方法来加快Maple的速度 .

我意识到如果没有所有的血腥细节，这可能很难回答，但每个功能的代码，例如 point 和 poly 已经过优化，所以这里真正的问题是，如果有更快的方法通过动态构建矩阵或类似的东西来获取行列式 .

更新：这是我玩过的两个不起作用的想法：

  • 我可以存储多项式（因为它们需要一段时间来计算，我不想重做，如果我可以帮助它）到长度为 n! 的向量中，并动态计算点，并将这些值插入到行列式的置换公式：

permutation determinant formula

这里的问题是矩阵的大小是 O(N!) ，所以对于我的情况，这将是 O((n!)!) . 当 n=10 ， (n!)! = 3,628,800! 这是大到甚至考虑做的方式 .

  • 使用LU分解计算行列式 . 幸运的是，我的矩阵的主对角线是非零的，所以这是可行的 . 由于这是矩阵大小的 O(N^3) ，因此更接近可行的 O((n!)^3) . 但问题是，它需要我存储整个矩阵，这会对内存造成严重压力，无需考虑运行时间 . 所以这也不起作用，至少不是没有更多的聪明 . 有任何想法吗？
algorithm permutation maple determinants

2 回答

  • -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 和 i 的 i 列，你只需要知道前一行/列向前移动 . 这样您就可以尽可能地并行处理并根据需要进行存储 . 由于您可以根据需要计算条目 a_ij ，因此需要存储两个长度为 n 的向量，同时生成另外两个长度为 n 的向量（ U 行， L 列） . 该算法需要 n^2 时间 . 您可能会找到更多技巧，但这取决于您的空间/时间权衡 .

    回复于
  • 2

    不确定我是否跟着你的问题;是（或它是否减少）以下？

    你有两个向量n个数字，称之为 x 和 c ，然后矩阵元素是 k 的 k 的产品，每个行/列对应于 x 和 c 的不同排序？

    如果是这样，那么我相信只要 x 或 c 中存在重复值，矩阵就会是奇异的，因为矩阵将具有重复的行/列 . 尝试在一个较小的 n 上使用不同的 x 和 c 来看一堆蒙特卡罗，以查看这种情况是否通常是非单数的 - 它对于6来说是真实的 - 对于10来说它是真的 .

    就蛮力而言，你的方法：

    • 不是首发

    • 可以更快地工作（对于 n=7 应该是几秒钟），但是你可能想要尝试SVD而不是LU，这会让你更好地了解矩阵的表现 .

    回复于

相关问题