I wrote this yesterday before my notebook broke down (which now seems to work
again) so it is slightly outdated by William's comments but still has some
more details:
---
Hi Simon,
You did nothing wrong and the function is not optimised yet but both doesn't
seem to be the reason. I replicated what kernel does below:
sage: M = MatrixSpace(GF(2),1000,500).random_element()
sage: time E = M.transpose().echelon_form()
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
sage: pivots = E.pivots()
sage: pivots_set = set(pivots)
sage: basis = []
sage: VS = sage.modules.free_module.VectorSpace
sage: R = M.base_ring()
sage: V = VS(R,M.nrows())
sage: ONE = R(1)
sage: for i in xrange(M.nrows()):
if not (i in pivots_set):
v = V(0)
for r in range(len(pivots)):
v[pivots[r]] = -E[r,i]
basis.append(v)
....:
sage: time W = V.subspace(basis)
CPU times: user 18.01 s, sys: 0.03 s, total: 18.04 s
Wall time: 18.04 s
So it seems the subspace command is really expensive here and dominates the
runtime. Th for loop also takes much longer than the transpose + echelon
form. FYI in the same time (18s) I can transpose + echelonize a 20000 x 20000
matrix:
sage: M = random_matrix(GF(2),20000,20000)
sage: time E = M.transpose().echelon_form()
CPU times: user 14.89 s, sys: 0.07 s, total: 14.96 s
Wall time: 15.02 s
so something is really going wrong here with subspace. FYI here is the %prun
1516188 function calls in 24.771 CPU seconds
750509 2.075 0.000 6.827 0.000 integer_mod_ring.py:597 ...
1500 1.292 0.001 5.706 0.004 free_module.py:505(__call__)
1 1.112 1.112 24.771 24.771 {method 'left_kernel' ...
2 0.129 0.065 0.130 0.065 matrix_space.py:916(matrix)
1 0.046 0.046 21.201 21.201 free_module.py:3202(__init__)
1 0.028 0.028 19.765 19.765 free_module.py:396 ...
2 0.025 0.012 14.039 7.020 matrix_space.py:243(__call__)
1 0.013 0.013 5.695 5.695 {method 'rows' ...
1500 0.012 0.000 5.719 0.004 free_module.py:3170(__call__)
500 0.009 0.000 0.011 0.000 free_module.py:1387(zero_vector)
500 0.006 0.000 0.006 0.000 {method '__copy__' ...
....
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: [EMAIL PROTECTED]
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
