The question is what distribution one is aiming for. Is there something special about GL(n, F) that we're trying to achieve? Otherwise, I think the generate-and-check, perhaps re-defining a single random entry on failure, is an evener distribution.
- Robert On Mon, Jul 2, 2012 at 3:32 PM, Martin Albrecht <martinralbre...@googlemail.com> wrote: > We should be able to do even better, right? > > Generate upper triangular + lower triangular matrix and do a product? > > > On Monday 02 Jul 2012, charles Bouillaguet wrote: >> Hi, >> >> I was wondering why some of my code was Dawn Slow (tm), and I ended up >> being surprised to notice that it was spending all its time trying to >> generate a random invertible matrix.... In particular, over finite >> fields, GL(N, GF(q)).random_element() is MUCH MUCH MUCH slower than >> the naive method that just generates a random matrix, checks if it is >> invertible, and tries again if it is not the case >> >> >> sage: %time GL(64, GF(2)).random_element() >> CPU times: user 20.47 s, sys: 2.64 s, total: 23.11 s >> Wall time: 28.93 s >> >> --> 30s is not a reasonable performance to generate a small random >> invertible matrix.... >> >> By the way, this fails with large primes. >> >> %time GL(64, GF(2^127-1)).random_element() >> .... >> TypeError: Unable to convert Gap element 'ZmodpZObj( >> 152551219330529388046437174479921365258, >> 170141183460469231731687303715884105727 )' >> error coercing to finite field >> >> I would suggest overloading GL(N, K).random_element() with the naive >> procedure when K is a finite field. >> >> def faster_random_invertible_matrix(n,K): >> S = matrix(K,n) >> while not S.is_invertible(): >> S = MatrixSpace(K,n,n).random_element() >> return S >> >> >> sage: %timeit faster_random_invertible_matrix(64, GF(2)) >> 125 loops, best of 3: 1.8 ms per loop >> >> ---> this is about 15000 times faster.... >> >> How do you feel about this ? It's not a bug stricto sensu, but >> math-oriented people might stumble across GL(N,K).random_element() and >> try to use it even is a much faster solution is available. >> -- >> Charles Bouillaguet > > Cheers, > Martin > > -- > name: Martin Albrecht > _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF > _www: http://martinralbrecht.wordpress.com/ > _jab: martinralbre...@jabber.ccc.de > > -- > 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 -- 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
