On Monday 15 February 2010, William Stein wrote: > On Sun, Feb 14, 2010 at 8:49 PM, Jeff Stroomer <[email protected]> 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: [email protected] -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
