Opened 11 years ago

Last modified 11 years ago

#10604 closed defect

Rewrite diagonal matrix constructor — at Version 23

Reported by: rbeezer Owned by: ddrake
Priority: minor Milestone: sage-4.6.2
Component: linear algebra Keywords:
Cc: ddrake Merged in:
Authors: Rob Beezer, Dan Drake Reviewers: Dan Drake, Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

Diagonal matrix constructor fails when given a tuple, and there is a request to support numpy arrays as input. This seems easiest to accomplish with a re-write and documentation upgrade.

NumPy array request: http://groups.google.com/group/sage-devel/browse_thread/thread/f0ecd06fcf9efb1b

sage: diagonal_matrix( (1,2,3) )
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/home/sage/sage-4.6.1.rc1/devel/sage-main/<ipython console> in <module>()

/home/sage/sage-4.6.1.rc1/local/lib/python2.6/site-packages/sage/matrix/constructor.pyc in diagonal_matrix(arg0, arg1, arg2, sparse)
   1271 
   1272     if ring is None:
-> 1273         return matrix(nrows, nrows, w, sparse=sparse)
   1274     else:
   1275         return matrix(ring, nrows, nrows, w, sparse=sparse)

/home/sage/sage-4.6.1.rc1/local/lib/python2.6/site-packages/sage/matrix/constructor.pyc in matrix(*args, **kwds)
    577                         ncols = len(args[0]) // nrows
    578                     elif ncols != len(args[0]) // nrows:
--> 579                         raise ValueError, "entries has the wrong length"
    580                 elif len(args[0]) > 0:
    581                     raise ValueError, "entries has the wrong length"

ValueError: entries has the wrong length

Apply:

Depends: #10626

Change History (26)

comment:1 Changed 11 years ago by rbeezer

  • Description modified (diff)

comment:2 Changed 11 years ago by rbeezer

  • Cc ddrake added

comment:3 Changed 11 years ago by rbeezer

  • Status changed from new to needs_review

Patch contains an overhaul of the diagonal_matrix() constructor, fixing at least one bug, and adding support for NumPy arrays as input. Two observations:

  1. Results are now sparse matrices by default. This is a change in behavior, but causes no doctest failures anywhere in the Sage library.
  1. Original doctests for this function will still pass. They are gone now, but were the last thing to be deleted and were fully tested.

comment:4 Changed 11 years ago by ddrake

  • Authors set to Rob Beezer
  • Reviewers set to Dan Drake

I read over the code and it looks nice. I love patches that add tons and tons of documentation! I'll run some doctests and make sure this works properly.

comment:5 Changed 11 years ago by ddrake

  • Owner changed from jason, was to ddrake

Hmm, this is weird:

sage: v = numpy.array([1,2,3,100000])
sage: m = diagonal_matrix(v)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/<ipython console> in <module>()

/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/local/lib/python2.6/site-packages/sage/matrix/constructor.pyc in diagonal_matrix(arg0, arg1, arg2, sparse)
   1392         if str(entries.dtype).count('complex')==1:
   1393             ring = CDF
-> 1394         v = [ring(x) for x in entries]
   1395     else:
   1396         raise TypeError('diagonal matrix entries are not a supported type (list, tuple, vector, or NumPy array)')

TypeError: 'NoneType' object is not callable

Your examples seem to have all RDF entries; my example has numpy int64 entries. Do you see what's going on here?

comment:6 follow-ups: Changed 11 years ago by ddrake

I'm also seeing a doctest failure:

drake@sage.math:/scratch/drake/days27/sage-4.6.1.rc1$ ./sage -t  devel/sage-main/sage/rings/number_field/number_field_ideal.p
y
sage -t  "devel/sage-main/sage/rings/number_field/number_field_ideal.py" 
**********************************************************************   
File "/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/devel/sage-main/sage/rings/number_field/number_field_ideal.py", line 1831
:
    sage: units=I.invertible_residues()
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_61[9]>", line 1, in <module>
        units=I.invertible_residues()###line 1831:
    sage: units=I.invertible_residues()
      File "/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/local/lib/python/site-packages/sage/rings/number_field/number_field_ideal.py", line 1846, in invertible_residues
        return self.invertible_residues_mod(subgp_gens=None, reduce=reduce)
      File "/mnt/usb1/scratch/drake/days27/sage-4.6.1.rc1/local/lib/python/site-packages/sage/rings/number_field/number_field_ideal.py", line 1929, in invertible_residues_mod
        A, U, V = M.smith_form()
      File "matrix2.pyx", line 7108, in sage.matrix.matrix2.Matrix.smith_form (sage/matrix/matrix2.c:37793)
      File "matrix2.pyx", line 7269, in sage.matrix.matrix2._smith_diag (sage/matrix/matrix2.c:39676)
      File "integer.pyx", line 5163, in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:28740)
      File "integer.pyx", line 367, in sage.rings.integer.as_Integer (sage/rings/integer.c:6052)
      File "integer.pyx", line 680, in sage.rings.integer.Integer.__init__ (sage/rings/integer.c:7312)
    TypeError: unable to coerce <class 'sage.rings.ideal.Ideal_pid'> to an integer

...and a bunch of similar failures in the same file.

comment:7 in reply to: ↑ 6 Changed 11 years ago by rbeezer

  • Status changed from needs_review to needs_work

Replying to ddrake:

Thanks, Dan. The int64 makes sense, I think I need to return the NumPy matrices sooner, and coerce them further. The Smith Normal Form certainly should involve diagonal matrices, but I can't quite see where that is coming from (and the failure was not evident in my tests run last night).

I'll get back to it again in a bit.

Rob

comment:8 in reply to: ↑ 6 Changed 11 years ago by rbeezer

Replying to ddrake:

I'm also seeing a doctest failure:

drake@sage.math:/scratch/drake/days27/sage-4.6.1.rc1$ ./sage -t  devel/sage-main/sage/rings/number_field/number_field_ideal.py

Smith Form seems to be unhappy about getting a sparse matrix:

sage: B=diagonal_matrix(ZZ, [3,4])
sage: B.is_sparse()
True
sage: B.smith_form()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

<snip>

TypeError: unable to coerce <class 'sage.rings.ideal.Ideal_pid'> to an integer

sage: C=B.dense_matrix()
sage: C.smith_form()
(
[ 1  0]  [ 1  1]  [-1 -4]
[ 0 12], [-4 -3], [ 1  3]
)

comment:9 Changed 11 years ago by rbeezer

Sparse integer matrices get sent to the generic Smith form routine (which I suspect is broken, #10625). It fails on an integer matrix. Solution is to direct sparse integer matrices to the dense version and report the generic version.

That change is at #10626, and this ticket will now depend on that patch.

comment:10 Changed 11 years ago by rbeezer

  • Status changed from needs_work to needs_review

v2 patch depends on #10626 to avoid the sparse/smith-form problem, and the numpy types are now all automatically handled by the prepare() method for free module elements. Passes tests in sage/matrix and I'll start full tests right now.

comment:11 Changed 11 years ago by rbeezer

This will likely depend on the following sequence:

4.6.1.rc1, #10364, #10537, #10626

comment:12 Changed 11 years ago by rbeezer

Passes all tests in devel/sage with patches described above, so I think this is ready now.

comment:13 Changed 11 years ago by ddrake

  • Status changed from needs_review to positive_review

Green light from the patchbot...code is good. Positive review.

Release manager: apply #10537 and #10626 first, then only attachment:trac_10604-diagonal-matrix-constructor-v2.patch.

comment:14 Changed 11 years ago by rbeezer

Hi Dan,

Thanks for your help with this and staying with it - much improved based on your testing (and I may be able to excise some NumPy-specific code in the vector constructor based on the prepare() experience here.

I missed seeing the green light. Dang. I've not been paying much attention to the patchbot since it would fail so often on the startup tests, but maybe that is fixed now.

Rob

comment:15 follow-ups: Changed 11 years ago by jdemeyer

  • Status changed from positive_review to needs_work

There are some doctest failures:

sage -t  "devel/sage/sage/rings/number_field/number_field_ideal.py"
**********************************************************************
File "/usr/local/src/sage-4.6.2.alpha1/devel/sage/sage/rings/number_field/number_field_ideal.py", line 2304:
    sage: I.ideallog(a + 7, [1+a, 2])
Exception raised:
    Traceback (most recent call last):
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[11]>", line 1, in <module>
        I.ideallog(a + Integer(7), [Integer(1)+a, Integer(2)])###line 2304:
    sage: I.ideallog(a + 7, [1+a, 2])
      File "/usr/local/src/sage-4.6.2.alpha1/local/lib/python/site-packages/sage/rings/number_field/number_field_ideal.py", line 2357, in ideallog
        mat = mat.stack( diagonal_matrix(ZZ, invs).augment(zero_matrix(ZZ, len(invs), len(gens))))
      File "matrix_integer_dense.pyx", line 4426, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.stack (sage/matrix/matrix_integer_dense.c:32907)
    TypeError: Cannot convert sage.matrix.matrix_integer_sparse.Matrix_integer_sparse to sage.matrix.matrix_integer_dense.Matrix_integer_dense
**********************************************************************
File "/usr/local/src/sage-4.6.2.alpha1/devel/sage/sage/rings/number_field/number_field_ideal.py", line 2306:
    sage: I.ideallog(a + 7, [2, 1+a])
Exception raised:
    Traceback (most recent call last):
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[12]>", line 1, in <module>
        I.ideallog(a + Integer(7), [Integer(2), Integer(1)+a])###line 2306:
    sage: I.ideallog(a + 7, [2, 1+a])
      File "/usr/local/src/sage-4.6.2.alpha1/local/lib/python/site-packages/sage/rings/number_field/number_field_ideal.py", line 2357, in ideallog
        mat = mat.stack( diagonal_matrix(ZZ, invs).augment(zero_matrix(ZZ, len(invs), len(gens))))
      File "matrix_integer_dense.pyx", line 4426, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.stack (sage/matrix/matrix_integer_dense.c:32907)
    TypeError: Cannot convert sage.matrix.matrix_integer_sparse.Matrix_integer_sparse to sage.matrix.matrix_integer_dense.Matrix_integer_dense
**********************************************************************
File "/usr/local/src/sage-4.6.2.alpha1/devel/sage/sage/rings/number_field/number_field_ideal.py", line 2313:
    sage: J.ideallog(5+2*b, [u, v], check=True)
Exception raised:
    Traceback (most recent call last):
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[17]>", line 1, in <module>
        J.ideallog(Integer(5)+Integer(2)*b, [u, v], check=True)###line 2313:
    sage: J.ideallog(5+2*b, [u, v], check=True)
      File "/usr/local/src/sage-4.6.2.alpha1/local/lib/python/site-packages/sage/rings/number_field/number_field_ideal.py", line 2357, in ideallog
        mat = mat.stack( diagonal_matrix(ZZ, invs).augment(zero_matrix(ZZ, len(invs), len(gens))))
      File "matrix_integer_dense.pyx", line 4426, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.stack (sage/matrix/matrix_integer_dense.c:32907)
    TypeError: Cannot convert sage.matrix.matrix_integer_sparse.Matrix_integer_sparse to sage.matrix.matrix_integer_dense.Matrix_integer_dense
**********************************************************************
File "/usr/local/src/sage-4.6.2.alpha1/devel/sage/sage/rings/number_field/number_field_ideal.py", line 2318:
    sage: I.ideallog(a + 7, [2])
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Given elements do not generate unit group -- they generate a subgroup of index 36
Got:
    Traceback (most recent call last):
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/usr/local/src/sage-4.6.2.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_71[18]>", line 1, in <module>
        I.ideallog(a + Integer(7), [Integer(2)])###line 2318:
    sage: I.ideallog(a + 7, [2])
      File "/usr/local/src/sage-4.6.2.alpha1/local/lib/python/site-packages/sage/rings/number_field/number_field_ideal.py", line 2357, in ideallog
        mat = mat.stack( diagonal_matrix(ZZ, invs).augment(zero_matrix(ZZ, len(invs), len(gens))))
      File "matrix_integer_dense.pyx", line 4426, in sage.matrix.matrix_integer_dense.Matrix_integer_dense.stack (sage/matrix/matrix_integer_dense.c:32907)
    TypeError: Cannot convert sage.matrix.matrix_integer_sparse.Matrix_integer_sparse to sage.matrix.matrix_integer_dense.Matrix_integer_dense
**********************************************************************

comment:16 in reply to: ↑ 15 Changed 11 years ago by ddrake

  • Status changed from needs_work to positive_review

Replying to jdemeyer:

There are some doctest failures:

The second-to-last comment says that you need to apply #10626 first.

comment:17 follow-up: Changed 11 years ago by rbeezer

Dan,

Did you try this against a very recent alpha? (4.6.2.alpha1 or better?). The failures look exactly like what happened on #4492, owing to #10443 that snuck in. (Wrong culprit listed on #4492).

I'm on the road so cannot check immediately, but will soon.

Thanks, Rob

comment:18 in reply to: ↑ 17 Changed 11 years ago by ddrake

  • Status changed from positive_review to needs_work

Replying to rbeezer:

Dan,

Did you try this against a very recent alpha? (4.6.2.alpha1 or better?). The failures look exactly like what happened on #4492, owing to #10443 that snuck in. (Wrong culprit listed on #4492).

I tried it against 4.6.2.alpha2, and I think I spoke too soon above...I applied #10626 and I'm still seeing the failure. So this does need some work, but (like Rob) I won't be able to do it in the next couple days.

comment:19 in reply to: ↑ 15 Changed 11 years ago by ddrake

Replying to jdemeyer:

There are some doctest failures:

The root of the problem is line 4426 in the stack() method in matrix_integer_dense.pyx:

cdef Matrix_integer_dense A = other

which works poorly when given a sparse matrix.

Interestingly, it works the other way around: you can stack a sparse matrix on top of a dense one. So we need to fix stack() for dense matrices.

Changed 11 years ago by ddrake

fix failing doctest in number_field_ideal.py

comment:20 follow-ups: Changed 11 years ago by ddrake

  • Status changed from needs_work to needs_review

Can someone who knows the matrix code take a look at my patch? All doctests pass with the two patches here applied to 4.6.2.alpha2.

comment:21 Changed 11 years ago by ddrake

  • Description modified (diff)

comment:22 in reply to: ↑ 20 Changed 11 years ago by rbeezer

Replying to ddrake:

Can someone who knows the matrix code take a look at my patch? All doctests pass with the two patches here applied to 4.6.2.alpha2.

Thanks, Dan. I'll look at this more carefully this evening - should have time then.

The root problem here is my decision to return a diagonal matrix as sparse since that is exposing a variety of inconsistencies. If I had it to do over....

Anyway, I suspect augment() suffers the same affliction. I jazzed up augment() on #10424 with a promise to sync up stack() so maybe I better make good on that.

Thanks for the detective work on this one.

Rob

comment:23 in reply to: ↑ 20 Changed 11 years ago by rbeezer

  • Authors changed from Rob Beezer to Rob Beezer, Dan Drake
  • Description modified (diff)
  • Reviewers changed from Dan Drake to Dan Drake, Rob Beezer
  • Status changed from needs_review to positive_review

Replying to ddrake:

Can someone who knows the matrix code take a look at my patch? All doctests pass with the two patches here applied to 4.6.2.alpha2.

Dan's patch looks good and with it, all tests pass. So I'll flip this back to positive review.

Thanks, Dan.

Note: See TracTickets for help on using tickets.