Shouldn't both give the same distribution mod p? Since every non-singular matrix A has a LU decomposition we should be able to just sample L and U separately to produce A?
On Monday 02 Jul 2012, Robert Bradshaw wrote: > 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 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
