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