Echelonize with transformation=True oddness for sparse matrix

[vbraun]

sage: matrix(ZZ, 3, 4, [1..12], sparse=False).echelon_form(transformation=True)
(
[ 1  2  3  4]  [ 0  2 -1]
[ 0  4  8 12]  [ 0  9 -5]
[ 0  0  0  0], [ 1 -2  1]
)
sage: matrix(ZZ, 3, 4, [1..12], sparse=True).echelon_form(transformation=True)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/vbraun/opt/sage-4.7.1.alpha3/devel/sage-main/<ipython console> in <module>()

/home/vbraun/Sage/sage/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.echelon_form (sage/matrix/matrix2.c:27633)()

/home/vbraun/Sage/sage/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.echelonize (sage/matrix/matrix2.c:27292)()

/home/vbraun/Sage/sage/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix._echelonize_ring (sage/matrix/matrix2.c:26560)()

TypeError: Cannot convert tuple to sage.matrix.matrix2.Matrix

Appy:

1. attachment: trac_11558_echelon_form_with_transformation.patch

Component: linear algebra

Author: Volker Braun

Reviewer: Rob Beezer

Merged: sage-4.7.2.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/11558

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:1

Volker,

Unfortunate - but at least it is fixed now. Passes tests in the obvious places, I'll run long tests overnight.

Comments, in decreasing order of merit.

1. Tests would benefit from a mention of the Trac ticket being fixed.

2. Do you want to document the transformation keyword in the docstring?

3. Internal logic of the echelon form code is a mystery to me, as is the code for creating/copying matrices. Since we are both in the neighborhood, is there a faster method for copying a matrix than the following?

for c from 0 <= c < self.ncols():
    for r from 0 <= r < self.nrows():
        self.set_unsafe(r, c, d.get_unsafe(r,c))

I don't know, just seems inefficient to go entry-by-entry. Not critical, just a thought. Long weekend here in the US, but I'll stick with this.

Rob

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

Reviewer: Rob Beezer

[vbraun]

comment:2

3. I think copying elementwise is necessary since the lhs and rhs matrices have potentially different storage order. In particular for sparse matrices, the echelon form is computed with dense matrices and then copied back to a sparse matrix.

It seems like hermite_form() is supposed to be an alias for echelon_form(). But sparse matrices don't have a hermite_form() method? I'll update the patch to fix that and also your points 1 & 2.

[vbraun]

Updated patch

[vbraun]

comment:3

Attachment: trac_11558_echelon_form_with_transformation.patch.gz

I've added more documentation. Some matrix backends don't support echelon_form(transformation=True), so eventually we should compute the transformation matrix from the pivots if necessary. I'll leave that for later :-)

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:4

Applies, builds, passes obvious tests on 4.7.1.alpha3. And looks good.

I'll run full tests overnight and then flip this to positive review.

Rob

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:5

Passes all long tests on 4.7.1.alpha3, so positive review. Thanks for cleaning this up.

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

Description changed:

--- 
+++ 
@@ -20,3 +20,6 @@

 TypeError: Cannot convert tuple to sage.matrix.matrix2.Matrix

+ +Appy: +1. [attachment: trac_11558_echelon_form_with_transformation.patch]

[jdemeyer]

Description changed:

--- 
+++ 
@@ -22,4 +22,4 @@

Appy: -1. [attachment: trac_11558_echelon_form_with_transformation.patch] +1. attachment: trac_11558_echelon_form_with_transformation.patch

[jdemeyer]

Merged: sage-4.7.2.alpha1