Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

but the a i,j should also be random following a uniform distribution in [0, k].

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.

The problem is that this check, for the 300x300 matrices takes something near 2 seconds, and I can't afford that.

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> The U[0,k] condition means that taken a set of matrices, each position (i , j) across the set should follow a uniform distribution.

like image 865
Dr. belisarius Avatar asked Feb 27 '11 07:02

Dr. belisarius


1 Answers

In both Matlab and Octave, the determinant and LU factorization of a 500x500 matrix are basically instantaneous. Does Mathematica have a mode where it can call out to LAPACK or some similar library? You might need to annotate that your arrays should be treated as floating point numbers and not symbolically; that might make it a lot faster. As a point of comparison, LU on a 5000x5000 matrix takes 8.66 seconds on my system using Octave; 500x500 should be around 1000 times faster than that.

like image 100
Jeremiah Willcock Avatar answered Sep 19 '22 17:09

Jeremiah Willcock