生成随机非奇异整数矩阵

Question

作为合成噪声生成算法的一部分，我必须动态构建许多大型非奇异方阵

a _i,j (i,j:1..n) / ∀ (i ,j) a _i,j ε ℤ 且 0 ≤ a _i,j ≤ k 且 Det[a] ≠ 0

但 a _{i,j 也应该是随机的，遵循 [0, k] 中的均匀分布。}

在当前的版本中，问题有 n ≅ 300，k≅ 100。

在 Mathematica 中，我可以非常快地生成随机元素矩阵，但问题是我还必须检查奇点。我目前正在使用行列式值。

问题是，对于 300x300 矩阵，此检查需要近 2 秒的时间，而我负担不起。

当然，我可以通过选择随机的第一行然后构造连续的正交行来构造行，但我不确定如何保证这些行的元素遵循 [0,k] 中的均匀分布。

我正在 Mathematica 中寻找解决方案，但也欢迎更快的生成矩阵的算法。

注意> U[0,k] 条件意味着采用一组矩阵，该组中的每个位置 (i , j) 应遵循均匀分布。

Answer 1

在 Matlab 和 Octave 中，500x500 矩阵的行列式和 LU 分解基本上都是瞬时的。 Mathematica 是否有一种可以调用 LAPACK 或类似库的模式？您可能需要注释您的数组应被视为浮点数而不是符号；这可能会让速度快很多。作为比较，在我使用 Octave 的系统上，5000x5000 矩阵上的 LU 需要 8.66 秒； 500x500 应该比这个快 1000 倍左右。

Answer 2

您可以使用 MatrixRank 代替。在我的机器上，对于大型 nxn 整数矩阵，速度大约快 n/10 倍。

Answer 3

如果在奇点测试中使用数值近似矩阵，您将获得更好的速度。

k = 100; n = 500;
mat = RandomInteger[100, {n, n}];

AbsoluteTiming[Det[mat] == 0]

Out[57]= {6.8640000, False}

AbsoluteTiming[Det[N@mat] == 0.] (*warning light!!*)

Out[58]= {0.0230000, False}

AbsoluteTiming[MatrixRank[N@mat] != n]

Out[59]= {0.1710000, False}

不幸的是，最快的测试并不可靠。但等级测试应该效果很好。这是一个简单的示例，其中我们用先前行的总和替换最后一行。

mat2 = mat;
mat2[[-1]] = Total[Most[mat]];

AbsoluteTiming[Det[mat2] == 0]

Out[70]= {9.4750000，True}

AbsoluteTiming[Det[N@mat2] == 0.]

Out[69]= {0.0470000，False}

AbsoluteTiming[MatrixRank[N@mat2] != n]

Out[71]= {0.1440000，True}

原则上，我认为排名测试给出假阴性的可能性很小。说是因为身体不好。由于您的使用可以更好地容忍误报（即，不正确的奇点声明），您可以改为测试素数模数的奇点。我认为这是其他人提出的建议之一。

继续上面的例子：

AbsoluteTiming[Det[mat, Modulus -> Prime[1000]]]

Out[77]= {0.6320000, 4054}

AbsoluteTiming[Det[mat2, Modulus -> Prime[1000]]]

Out[78]= {0.6470000, 0}

这很慢，但比处理有理数更快。就其价值而言，对于大多数用途，我对通过 MatrixRank[N[matrix]] 进行更快测试的结果相当有信心。

丹尼尔·利希布劳
沃尔夫勒姆研究公司

Answer 4

这是我所做的评论的扩展。我同意 Dan 的观点，即数字版本返回误报的可能性极小。尽管如此，如果最小奇异值大于某个误差容限，您可以通过检查奇异值并可靠地返回 False 来避免这种情况。 （诚​​然，找到可证明的容差可能有点棘手。）如果最小奇异值小得令人不舒服，则可以将 Det 应用于整数矩阵。

对于大多数非奇异矩阵，这是一个应该快速返回 False 的函数。如果矩阵接近奇异，则执行更昂贵的整数计算。

singularQ[M_?MatrixQ] := If[
  Last[SingularValueList[N[M], Tolerance -> 0]] > 1/10.0^8,
 False, Det[M] == 0];

这里有 200 个符合您描述的矩阵。中间的一个已被操纵为单一的。

SeedRandom[1];
matrices = RandomInteger[{0, 100}, {200, 300, 300}];
matrices[[100, -1]] = Sum[RandomInteger[{0, 10}]*matrices[[100, k]],
 {k, 1, Length[matrices[[100]]] - 1}];

现在，让我们一边观察一边找出所有奇异矩阵的索引。

Flatten@Monitor[Table[
  If[singularQ[matrices[[k]]], k, {}],
  {k, 1, Length[matrices]}], k]