生成随机的非奇异整数矩阵 [英] Generating Random Non-Singular Integer Matrices
问题描述
作为一种人工合成的噪音生成算法的一部分，我要构建移动很多大非奇异方阵
As part of a synthetic noise generation algorithm, I have to construct on the fly a lot of large non-singular square matrices
在<子> I，J （I，J：1 ... N）/＆FORALL; （I，J）一<子> I，J ＆ISIN代码; ℤ和0乐;一个<子> I，J 和乐; k和挪威[A] NE; 0
a i,j (i,j:1..n) / ∀ (i,j) a i,j ∈ ℤ and 0 ≤ a i,j ≤ k and Det[a] ≠ 0
但一<子> I，J 也应该是随机的以下在[0，k]的均匀分布。
but the a i,j should also be random following a uniform distribution in [0, k].
在当前的版本问题有n＆琮; 300，K＆琮; 100。
In its current incarnation the problem has n ≅ 300, k≅ 100.
在数学，我可以非常快速生成随机单元矩阵，但问题是，我还必须检查的奇点。我目前使用的行列式的值这一点。
In Mathematica, I can generate random element matrices very fast, but the problem is that I must also check for singularity. I am currently using the Determinant value for this.
现在的问题是，这种检查，为300×300的矩阵需要近2秒东西，我不能说。
The problem is that this check, for the 300x300 matrices takes something near 2 seconds, and I can't afford that.
当然，我可以构造的行选择一个随机的第一行，然后构建连续的正交行，但我不知道如何来保证这些行将具有以下在[0，K]均匀分布的元素。
Of course I may construct the rows by selecting a random first row and then constructing successive orthogonal rows, but I'm not sure how to guarantee that those rows will have their elements following an uniform distribution in [0,k].
我要寻找一个在数学的解决方案，而只是一个更快的算法生成矩阵也是欢迎的。
I am looking for a solution in Mathematica, but just a faster algorithm for generating the matrices is also welcome.
NB>的U [0，K]的条件是指拍摄了一组矩阵，在整个集中的每个位置（I，J）应遵循的均匀分布。
NB> The U[0,k] condition means that taken a set of matrices, each position (i , j) across the set should follow a uniform distribution.
推荐答案
如果您在奇点测试用数字大致矩阵，您将得到更好的速度。
If you use numeric approximate matrices in the singularity tests you will get much better speed.
k = 100; n = 500;
mat = RandomInteger[100, {n, n}];
AbsoluteTiming[Det[mat] == 0]
专家[57] = {6.8640000，假}
Out[57]= {6.8640000, False}
AbsoluteTiming[Det[N@mat] == 0.] (*warning light!!*)
专家[58] = {0.0230000，假}
Out[58]= {0.0230000, False}
AbsoluteTiming[MatrixRank[N@mat] != n]
专家[59] = {0.1710000，假}
Out[59]= {0.1710000, False}
不幸的是最快的检测是不可靠的。但是，秩和检验应该很好地工作。下面是一个简单的例子，其中我们替换了最后一排由前行的总和。
Unfortunately that fastest test is not reliable. But the rank test should work well. Here is a quick example wherein we replace the last row by the sum of prior rows.
mat2 = mat;
mat2[[-1]] = Total[Most[mat]];
AbsoluteTiming[Det[mat2] == 0]
专家[70] = {9.4750000，真}
Out[70]= {9.4750000, True}
AbsoluteTiming[Det[N@mat2] == 0.]
专家[69] = {0.0470000，假}
Out[69]= {0.0470000, False}
AbsoluteTiming[MatrixRank[N@mat2] != n]
专家[71] = {0.1440000，真}
Out[71]= {0.1440000, True}
在原则上，我想有一个短小机会，秩和检验可以给一个假阴性，说由于病调理。由于您的使用情况将更好地耐受误报（即奇不正确的索赔），你可以改为在一个质数模测试奇点。我想，这是其他人提出的建议之一。
In principle I suppose there is a smallish chance that the rank test could give a false negative., say due to ill conditioning. As your usage will better tolerate false positives (that is, incorrect claims of singularity) you could instead test for singularity over a prime modulus. I think this was one of the recommendations others have made.
继续上述的例子：
AbsoluteTiming[Det[mat, Modulus -> Prime[1000]]]
专家[77] = {0.6320000，4054}
Out[77]= {0.6320000, 4054}
AbsoluteTiming[Det[mat2, Modulus -> Prime[1000]]]
专家[78] = {0.6470000，0}
Out[78]= {0.6470000, 0}
这是缓慢的，但不是工作在有理数更快。对于它的价值，对于大多数使用情况，我会相当有信心，在较快的测试结果通过MatrixRank [N [矩阵]
This is slow but faster than working over the rationals. For what it's worth, for most usage I'd be fairly confident in the outcomes of the faster testing via MatrixRank[N[matrix]].
丹尼尔Lichtblau 沃尔夫勒姆研究
Daniel Lichtblau Wolfram Research
这篇关于生成随机的非奇异整数矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
