On Tue, Jul 3, 2012 at 10:12 AM, Javier López Peña <vengor...@gmail.com> wrote: > Hi Robert, > > > On Tuesday, July 3, 2012 5:21:53 PM UTC+1, Robert Bradshaw wrote: >> >> You don't have to re-generate the entire matrix, you could likely get >> away with changing one random element at a time. (And if you did so, >> perhaps computing the rank would be cheaper). Still, +1 to it's much >> faster than what we have now and still easy to implement. > > > A naive implementation of this idea doesn't quite work, setting: > > def faster_random_invertible_matrix(n,K): > M = MatrixSpace(K,n,n) > S = M.random_element() > while not S.is_invertible(): > S = M.random_element() > return S > > def faster_random_invertible_matrix2(n,K): > M = MatrixSpace(K,n,n) > S = M.random_element() > while not S.is_invertible(): > i = randint(0,n-1) > j = randint(0,n-1) > S[i,j] = K.random_element() > return S > > yields the following test results: > > sage: %timeit faster_random_invertible_matrix(200, GF(2)) > 625 loops, best of 3: 792 µs per loop > sage: %timeit faster_random_invertible_matrix2(200, GF(2)) > 125 loops, best of 3: 1.59 ms per loop > > I think changing the matrix elements one by one might be a bad idea in cases > where there is a single row that is a multiple of another one, as the chance > of hitting the offending row is 1/n and the rank gets recomputed every time. > > Unless there is a faster way of computing the rank taking advantage of > previously used computations, that is.
You're right, one does want to ensure that there's a high probability of changing its rank. One could also change O(n) entries (one on each row/column) rather than all O(n^2). This will have a larger impact for large fields (where the per-element entropy is high, and GF(2) is a worst-case as individual-element-setting is expensive). But I suppose in those cases you're unlikely to hit a non-invertible matrix in the first place. - Robert -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
