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
