On Saturday 28 January 2012, Benjamin Howard wrote: > Hi -- > > I have an application in mind where I desperately > need a faster implementation of the matrix methods: > > matrix_from_columns > matrix_from_rows_and_columns > matrix_from_rows > > I am aware that these will not be as fast as the submatrix method (for > contiguous > submatrices) but the above three methods are still too slow by far... > > I'm hoping that someone could spend a little bit of time to write > faster versions of these (maybe > just cythonize them...)? I do not know how to do this myself or I'd > be glad to. Just to give an idea of how slow they are currently, see > below: > > #my own ad hoc matrix_from_columns: > def My_matrix_from_columns(mat,cols): > set_all_cols = set(range(mat.ncols())) > set_compl_cols = set_all_cols.difference(set(cols)) > compl_cols = list(set_compl_cols) > all_cols = cols + compl_cols > all_cols_one_up = [j+1 for j in all_cols] > p = sage.combinat.permutation.Permutation(all_cols_one_up) > p_matrix = p.to_matrix() > mat_perm = mat * p_matrix > return mat_perm.submatrix(0,0,mat_perm.nrows(),len(cols)) > > (I'm running sage-4.8, compiled from source on a pretty basic desktop > computer) > > sage: M = Matrix(GF(2),5000,5000); M.randomize() > sage: L = range(5000); shuffle(L); L = L[:2500] > sage: time N = M.matrix_from_columns(L) > Time: CPU 2.72 s, Wall: 2.73 s > sage: time N2 = My_matrix_from_columns(M,L) > Time: CPU 0.43 s, Wall: 0.45 s > > Surely, going to all the trouble of building that permutation matrix > after constructing > the complement to L in range(M.ncols()) (and adding one to get a valid > permutation > which unfortunately isn't 0-based), then, > multiplying by the permutation matrix, > then extracting the contiguous submatrix, seems like it should have > been slower > than the native method from the matrix class?
How soon do you need it? I'm asking because I don't know how soon I could make this happen, but I'm sure we can make this much much faster by doing this in the M4RI library itself, i.e., in C. Do you know a bit of C? 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 email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
