[sage-devel] Re: Fastest way to multiply vector with matrix?
Hi! On 2015-02-17, Peter Bruin wrote: >> "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. This would play a role if you access elements of the matrices. However, if you do multiplication then only the underlying backend would be used, hence, the elements of the matrix will not be stored as Sage objects. But there is another source of overhead. I know that there are cdef methods (in sage.structure.element.Matrix) that allow one to do a matrix-by-matrix computation in situations where you are sure that both arguments are matrices of the same type over the same field and of matching dimensions. So, this already reduces some overhead. But if I understand correctly, it would still take the dimensions of the matrices into account and would then choose the suitable multiplication algorithm (if large enough: Use Strassen-Vinograd, otherwise: Use "naive" multiplication). What I do not know (and could not find): Is there a cdef method that allows you to specify that 1) the dimensions, base rings and implementations of both factors match, 2) you do want "naive" multiplication and certainly not anything fancy, and 3) one factor actually is a vector. In other words, I wonder whether there is (and if not, whether there should be) a method that is part of the Cython interface of Sage matrices that allows you to access the matrix-times-vector implementation of the underlying backend with virtually no overhead. >> 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 Perhaps worth trying. Thank you for your hints! Simon -- 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.
[sage-devel] Re: Fastest way to multiply vector with matrix?
Hi Martin, On 2015-02-17, Martin Albrecht wrote: > over GF(2) it helps to multiply from the left: Indeed. And GF(2) actually is a case where MeatAxe matrices are slower than the Sage standard. Over other fields (where MeatAxe matrices are faster, I just checked it over GF(5)) it holds still true that multiplication from the left is faster. Hm. I do have right modules, but of course I could still write it so that the matrices are multiplied from the left. Thanks for your hint! Simon -- 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.
[sage-devel] Re: Fastest way to multiply vector with matrix?
You can deamortise matrix-matrix multiplication to get better than quadratic time for matrix-vector multiplication if you allow precomputation. Probably not relevant here though. On Tuesday, 17 February 2015 18:40:40 UTC+1, Peter Bruin wrote: > > 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.
[sage-devel] Re: Fastest way to multiply vector with matrix?
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.
[sage-devel] Re: Fastest way to multiply vector with matrix?
On Tuesday, February 17, 2015 at 9:06:30 AM UTC-8, Simon King wrote: > > Hi! > > 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). > No immediate tips, but a pointer to an old ticket dealing with possibly related problems, to which you have contributed quite a bit in the past (not the problems, the ticket): http://trac.sagemath.org/ticket/15104 -- 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.
