For really fast generics I think you may need some kind of jit. Are generics handled by cython code or python code in sage? Does it cache anything?
I recently encountered similar problems anyhow. A generic rref took 20 minutes to reduce a tiny (by my standards) matrix as part of a factoring algorithm I was helping someone prototype. It should have been instantaneous (this was factoring a 14 term bivariate poly with total degree less than about 6). My answer to this for my own research is a generic layer in C for my own C code. It's some small factor slower than something handwritten, which, if I don't bother caching lookups, will probably be an increasing factor depending on how many types my generics handle. But it is acceptable for prototyping. As far as Sage is concerned, I'm not seeing the technical obstacle to Sage looking like this: C libraries (primitives) <-- Cython generics and generic algorithms <-- Python user language I can't believe Sage doesn't even factor bivariate polynomials over GFp after all these years. Why? Cause no one implemented it in Pari. It's completely broken in Singular. It would be way too slow in Python. And presumably some of the types you need to implement this algorithm are themselves way too slow cause they are currently implemented in python not cython, or they look up way too much stuff. Feel free to continue on sage.flame. CC'd there to save someone else doing it for me. Bill. On Sep 11, 4:22 am, dmharvey <dmhar...@cims.nyu.edu> wrote: > On Sep 10, 9:08 pm, Robert Bradshaw <rober...@math.washington.edu> > wrote: > > > sage: type(matrix(Integers(3^5), 5, 5)) > > <type 'sage.matrix.matrix_modn_dense.Matrix_modn_dense'> > > sage: type(matrix(Integers(3^20), 5, 5)) > > <type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'> > > That certainly explains one of the issues. > > Now watch me try to work around it: > > sage: R = Integers(3^20) > sage: M1 = Matrix([[R.random_element() for i in range(100)] for j in > range(100)]) > sage: M2 = Matrix([[R.random_element() for i in range(100)] for j in > range(100)]) > sage: M3 = M1 * M2 # 876 ms > sage: M1_lift = Matrix(ZZ, [[M1[i,j].lift() for i in range(100)] for j > in range(100)]) # 23.3 ms > sage: M2_lift = Matrix(ZZ, [[M2[i,j].lift() for i in range(100)] for j > in range(100)]) > sage: M3_lift = M1_lift * M2_lift # 41.4 ms > sage: M3 = Matrix(R, [[R(M3_lift[i,j]) for i in range(100)] for j in > range(100)]) # 555 ms!! > > So I can save 25% this way --- whereas if it were done properly I > would save a factor of about 20, and if I used Magma I would save a > factor of maybe 80. The only way to get a significant speedup without > modifying Sage is to keep all my matrices over Z and keep reducing on > every multiplication. It gets very messy. Especially when I want all > this code to work over extension rings too (but maybe we should ignore > that for now!) > > > > (Or maybe you mean "what aspects of Magma's development history and/or > > > development model led to these operations being fast"? That would be a > > > much longer conversation.) > > > That's what I would be interested in hearing your opinions on. My > > quick take is that no-one has needed/wanted this to be fast yet. > > Hard to tell. I've run into some of these things before, and not put > in the time to report them properly or fix them. It's a bit of a > chicken-and-egg thing; if someone new tries Sage and gives up because > of a performance problem like this, we might never hear from them. > Clearly someone at Magma thought they were important enough to make > fast, which suggests that at least some people using Magma (or people > *at* Magma) needed them to be fast. Certainly next time I work on a > project of non-trivial size like this, I will study the performance of > the relevant primitives in Sage before committing much time to writing > Sage code! > > david -- 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
