William, Martin, I guessed there was some magic in the machinery that does row echelon reductions. That was part of the reason I thought the row-echelon approach might be faster.
It's easy enough for me to substitute my own naive code to do the row echelon reductions, and see how that affects the speed. I'm also going to try using sparse matrices. Is there any easy way for me to count multiplications and additions when reduce() is used to do a Groebner basis reduction? If not, then how easy would it be to count multiplications and additions if I write my own version of reduce(), but use the normal multiplication and addition operations on polynomials? Jeff On Feb 15, 3:24 am, Martin Albrecht <m...@informatik.uni-bremen.de> wrote: > On Monday 15 February 2010, William Stein wrote: > > > > > On Sun, Feb 14, 2010 at 8:49 PM, Jeff Stroomer <jstroom...@hotmail.com> > wrote: > > > William, > > > > I used GF(101), GF(1009), and GF(1000099). > > > > Jeff > > > In Sage, echelon form over at least the first two of these fields uses > > the C++ Linbox library. That library in turn does computation of > > echelon forms using a very complicated asymptotically fast > > Strassen-style block algorithm that reduces the problem to clever use > > of matrix multiplications. Matrix multiplication over finite fields > > is in turn done using yet another Strassen-based algorithm that > > reduces matrix mutiplication over a finite field to many matrix > > multiplications with floating point numbers, which is typically done > > using ATLAS. ATLAS itself can be tuned in many ways, depending on > > hardware, whether Sage is installed from a binary or source, etc., > > which can easily cause up to a factor of 5 (or so) in performance. > > > Anyway, the point of the above remark is just that the actual default > > algorithm used for echelonization of a matrix over a finite field in > > Sage is probably much, much more complicated than you might at first > > guess. > > Also, if you don't explicitly specify that you want a sparse matrix your > matrix will be densely represented, while multivariate polynomials are always > sparse-ly represented (by a list of monomials). > > 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://www.informatik.uni-bremen.de/~malb > _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
