Hi Simon, > I have vectors (say, nx1 matrices) over finite fields, and I have nxn > matrices, by which I want ot multiply the vectors. > If I am taking the default matrix implementations for fields GF(2), > GF(4), GF(5) and GF(25), the timings are considerably worse than when > taking my age-old wrapper for an age-old matrix implementation in > C-MeatAxe (which is part of my group cohomology spkg).
Yes, linear algebra over finite fields in Sage is unacceptably slow... > "Asymptotically fast multiplication" doesn't seem relevant here. Indeed, the classical algorithm is the optimal way to multiply a matrix by a vector. > So I wonder: Is there perhaps some overhead killing the performance? Absolutely; the fact that all finite field elements are wrapped in Sage objects costs a lot of time. > What would you recommend as the fastest way in Sage to multiply a > vector with a matrix over small finite not necessarily prime fields? I would recommend merging one of Jeroen's branches to upgrade to a more recent PARI version (#16997 or #16939). These PARI versions contain improvements to linear algebra over finite fields that I made some time ago. Then given a matrix M and a vector v over a finite field, the following will probably give a nice speedup over M * v: sage: Mp = M._pari_() sage: vp = v._pari_().mattranspose() sage: Mp * vp The PARI version that Jeroen's ticket currently uses does not yet contain an even faster algorithm using Kronecker substitution; this was only merged in the PARI Git repository a week ago. It may be even faster (but much more work) to write classes for matrices and vectors over finite fields using FLINT (see also #16664 for the finite fields themselves). Peter -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
