Le mardi 3 juillet 2012 13:12:43 UTC-4, Javier López Peña a écrit : > > 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. > > And it is also not entirely clear to me why implementation 2 would not affect the random distribution.
> Unless there is a faster way of computing the rank taking advantage of > previously used computations, that is. > > Javier > -- 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
