生成随机非奇异整数矩阵

Question

作为合成噪声生成算法的一部分,我必须在运行中构建许多大的非奇异平方矩阵

一个_I,J(I,J:1..N)/∀(I,J)一个_I,J ∈ℤ和0≤一个_I,J ≤k和挪威并[a]≠0

但是a _i,j在[0,k]中均匀分布后也应该是随机的.

在目前的化身中,问题是n≅300,k≅100.

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

问题是这个检查,对于300x300矩阵需要2秒左右的时间,我负担不起.

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

我正在寻找Mathematica的解决方案,但也欢迎使用更快的生成矩阵的算法.

NB> U [0,k]条件意味着采用一组矩阵,整个集合中的每个位置(i,j)应遵循均匀分布.

Answer 1

在Matlab和Octave中,500x500矩阵的行列式和LU因子分解基本上是瞬时的.Mathematica有一个可以调用LAPACK或类似库的模式吗？您可能需要注释您的数组应该被视为浮点数而不是符号; 这可能会让它快得多.作为比较,使用Octave在我的系统上使用5.8x5000矩阵的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]

输出[57]= {6.8640000，假}

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

输出[58]= {0.0230000，假}

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

输出[59]= {0.1710000，假}

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

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

AbsoluteTiming[Det[mat2] == 0]

输出[70]= {9.4750000，真}

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

输出[69]= {0.0470000，假}

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

输出[71]= {0.1440000，真}

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

继续上面的例子：

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

输出[77]= {0.6320000, 4054}

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

输出[78]= {0.6470000, 0}

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

Daniel Lichtblau 沃尔夫勒姆研究公司