[sage-devel] Re: Is left_kernel_matrix missing intentionally?
On Thursday, June 7, 2012 11:46:57 PM UTC-7, Nils Bruin wrote: > > That would be the *ONLY* reason. In general it seems that Sage vectors > have a slight preference to being row vectors (if you pass "matrix" a > list of vectors, they are interpreted as rows), so returning a matrix > with the appropriate row space is quite defendable. Sage vectors are a > bit ambivalent towards their orientation as can be seen how they > behave wrt multiplication on either side of a matrix. > > For applications of right_kernel_matrix, it's a complete toss-up > whether you need the rows or the transpose of that. Kernels are just > as often used to find a complement of a subspace as they are to > compute a matrix with prescribed (left)kernel. So, we should just do > what is most efficient, subject to being consistent. > Sage had a historical preference for rows, though vectors have often seemed neutral. Work the past two years has made columns better represented, and vectors more neutral, but ties are always won by rows. I've never understood the matrix constructor routines well enough to know if rows are to be prized when it comes to building matrices. So this preference for rows would be an explanation for the matrix in question having rows with meaning. But I am equally (or perhaps more) sympathetic to John's argument about the relevant matrix product being the zero matrix. In the end, I think rows won the tie and it meant fewer changes to legacy code. To get back to the original question. I don't think there is any reason *not* to have a "left_kernel_matrix()", even if it was consciously not built originally. But maybe we should have it return the matrix with the basis vectors as columns? (Just kidding in that last part!) Rob -- 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
Re: [sage-devel] Re: Is left_kernel_matrix missing intentionally?
I'm not sure I agree with the "ONLY" below. One could argue that the right kernel matrix of A should at least be a matrix B such that A*B=0 (and with other properties, of course, something like any other B' with A*B'=0 should have the form B'=B*C for some C...). John On 8 June 2012 07:46, Nils Bruin wrote: > On Jun 7, 10:29 pm, Rob Beezer wrote: >> I would be in favor of a right kernel matrix having its vectors as >> columns. It looks like this would save some transposes on the exit from >> the actual routines doing the computations. > > That would be the *ONLY* reason. In general it seems that Sage vectors > have a slight preference to being row vectors (if you pass "matrix" a > list of vectors, they are interpreted as rows), so returning a matrix > with the appropriate row space is quite defendable. Sage vectors are a > bit ambivalent towards their orientation as can be seen how they > behave wrt multiplication on either side of a matrix. > > For applications of right_kernel_matrix, it's a complete toss-up > whether you need the rows or the transpose of that. Kernels are just > as often used to find a complement of a subspace as they are to > compute a matrix with prescribed (left)kernel. So, we should just do > what is most efficient, subject to being consistent. > > (In fact I ran into the fact that left_kernel_matrix was missing > because I wanted to compute a matrix with prescribed right kernel) > > -- > 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 -- 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
[sage-devel] Re: Is left_kernel_matrix missing intentionally?
On Jun 7, 10:29 pm, Rob Beezer wrote: > I would be in favor of a right kernel matrix having its vectors as > columns. It looks like this would save some transposes on the exit from > the actual routines doing the computations. That would be the *ONLY* reason. In general it seems that Sage vectors have a slight preference to being row vectors (if you pass "matrix" a list of vectors, they are interpreted as rows), so returning a matrix with the appropriate row space is quite defendable. Sage vectors are a bit ambivalent towards their orientation as can be seen how they behave wrt multiplication on either side of a matrix. For applications of right_kernel_matrix, it's a complete toss-up whether you need the rows or the transpose of that. Kernels are just as often used to find a complement of a subspace as they are to compute a matrix with prescribed (left)kernel. So, we should just do what is most efficient, subject to being consistent. (In fact I ran into the fact that left_kernel_matrix was missing because I wanted to compute a matrix with prescribed right kernel) -- 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
Re: [sage-devel] Re: Is left_kernel_matrix missing intentionally?
So William knows my memory is faulty, and I finally overcame my own
laziness and looked at the code (and the ticket where this originated,
http://trac.sagemath.org/sage_trac/ticket/10746). IML, PARI, Sage generic
code produce right kernels. These come in different formats, so one option
for the right_kernel_matrix() function is to do no extra processing of the
result by asking for a "computed" basis. ('padic' uses IML.)
sage: A = matrix(ZZ,
[[-1, 0, -2, 2, -3],
[1, -1, 4, 0, 0],
[2, -2, 8, 0, 0],
[0, -2, 4, 4, -6]])
sage: A.right_kernel_matrix(algorithm='padic', basis='computed')
[ 2 -2 -1 0 0]
[-2 -2 0 -1 0]
[ 3 3 0 0 -1]
sage: A.right_kernel_matrix(algorithm='pari', basis='computed')
[-1 -1 0 1 1]
[ 1 1 0 2 1]
[-2 2 1 0 0]
Over fields, the results of a "basis matrix" of a kernel are a list of
vectors as rows, echelonized, whereas the computed basis of the Sage
generic code comes naturally (and simply) from the echelon form.
sage: A.change_ring(QQ).right_kernel_matrix(algorithm='generic',
basis='computed')
[-2 2 1 0 0]
[ 2 2 0 1 0]
[-3 -3 0 0 1]
sage: A.change_ring(QQ).right_kernel().basis_matrix()
[ 10 -1/40 -1/6]
[ 01 1/40 -1/6]
[ 0001 2/3]
The existing code before the ticket had a "_right_kernel_matrix()" over the
integers, which was called one place
(sage/algebras/quatalg/quaternion_algebra.py) and this was the model for
the new non-underscore method which replaced it (available for almost any
ring).
Previously Sage had a preference for left kernels, so a matrix would be
transposed *before* the call to a specialized procedure that was designed
to compute right kernels. For a right kernel, the matrix would be
transposed to compute a left kernel, then transposed again to be correct
input for the routine. I think this inefficiency is now gone.
I would be in favor of a right kernel matrix having its vectors as
columns. It looks like this would save some transposes on the exit from
the actual routines doing the computations. In refactoring, I was
concentrating on the organization of the code and packaging of the results,
so left a lot of things alone. It looks to me now like some of this old
code could be made more efficient in terms of packaging the results.
However, changing the format of an output of a function like this,
especially for square matrices, would probably be unwise.
Anyway, short answer is that there looks to be some room for further
(minor) improvements. But you'd have to look at the code.
Rob
--
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
Re: [sage-devel] Re: Is left_kernel_matrix missing intentionally?
On 2012-06-05 18:15, Nils Bruin wrote: > Interesting! On the other hand, from what I can tell from the Pari > documentation, their matrices are stored by columns. So if sage mainly > works with matrices stored by rows, then conversion between Pari and > Sage would most naturally involve a transposition. That means that > right_kernel_matrix(algorithm="pari") could be very efficient with its > present API. It might need a custom conversion routine, though. If no > care is taken, we can easily end up doing the equivalent of 2 > transpositions in the conversion (and/or allocation of unnecessary > intermediate forms). I'm too lazy to look it up now in the Sage sources, but I know that there are 2 different functions to convert between Sage and PARI matrices, one normal and one transposed. Apart from processor cache issues, these 2 conversion routines should be equally fast. -- 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
[sage-devel] Re: Is left_kernel_matrix missing intentionally?
On Jun 5, 8:57 am, William Stein wrote: > REMARK: Pari doesn't: > > ? matker([1,1;1,1]) > %3 = > [-1] > [1] > > That's a basis as columns. Interesting! On the other hand, from what I can tell from the Pari documentation, their matrices are stored by columns. So if sage mainly works with matrices stored by rows, then conversion between Pari and Sage would most naturally involve a transposition. That means that right_kernel_matrix(algorithm="pari") could be very efficient with its present API. It might need a custom conversion routine, though. If no care is taken, we can easily end up doing the equivalent of 2 transpositions in the conversion (and/or allocation of unnecessary intermediate forms). -- 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
Re: [sage-devel] Re: Is left_kernel_matrix missing intentionally?
On Mon, Jun 4, 2012 at 10:13 PM, Rob Beezer wrote: > Dear Nils, > > > On Thursday, May 31, 2012 4:16:59 PM UTC-7, Nils Bruin wrote: >> >> I noticed that matrices do have a left_kernel method but not a >> left_kernel_matrix. Is that intentional? > > > Short answer: yes, it was intentional. > > Long answer: about 16 months ago, I totally refactored the matrix kernel > code - a project on my list from since I first delved into the Sage > sources. It had become a bit of a rat's nest. Sometimes a matrix was > transposed twice before a real algorithm dealt with it. > > Most of the base computational routines (IML, PARI, iirc) produce a right > kernel matrix with the basis elements as rows, as unnatural as that may be. REMARK: Pari doesn't: ? matker([1,1;1,1]) %3 = [-1] [1] That's a basis as columns. > It is a consequence of getting the kernel from the echelon form, and then > packaging the vectors as rows. So I made this the hub between the actual > computations and conveniences, like kernels as vector spaces. You will have > noticed that a "plain" kernel is a left kernel. My intention was: if you > knew what you wanted, then the least overhead route to the basic computation > of a kernel was to request this "right kernel matrix." If you wanted to > ship it a transpose, that was your business, since you knew what you were > doing (presumably), and you were prepared to deal with the output properly > in whatever form you got it. > > Rob > > -- > 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 -- William Stein Professor of Mathematics University of Washington http://wstein.org -- 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
[sage-devel] Re: Is left_kernel_matrix missing intentionally?
Dear Nils, On Thursday, May 31, 2012 4:16:59 PM UTC-7, Nils Bruin wrote: > > I noticed that matrices do have a left_kernel method but not a > left_kernel_matrix. Is that intentional? > Short answer: yes, it was intentional. Long answer: about 16 months ago, I totally refactored the matrix kernel code - a project on my list from since I first delved into the Sage sources. It had become a bit of a rat's nest. Sometimes a matrix was transposed twice before a real algorithm dealt with it. Most of the base computational routines (IML, PARI, iirc) produce a right kernel matrix with the basis elements as rows, as unnatural as that may be. It is a consequence of getting the kernel from the echelon form, and then packaging the vectors as rows. So I made this the hub between the actual computations and conveniences, like kernels as vector spaces. You will have noticed that a "plain" kernel is a left kernel. My intention was: if you knew what you wanted, then the least overhead route to the basic computation of a kernel was to request this "right kernel matrix." If you wanted to ship it a transpose, that was your business, since you knew what you were doing (presumably), and you were prepared to deal with the output properly in whatever form you got it. Rob -- 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
