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
--
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
