Opened 11 years ago

Closed 11 years ago

#9720 closed enhancement (fixed)

Add random echelonizable matrices to matrix/constructor.py

Reported by: bwonderly Owned by: jason, was
Priority: major Milestone: sage-4.6
Component: linear algebra Keywords:
Cc: rbeezer, jason Merged in: sage-4.6.alpha1
Authors: Billy Wonderly Reviewers: David Joyner
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Adds two routines. One creates random matrices in echelon form to be used in other routines to be added later. The other creates random matrices whose echelon form has desirable properties, with the help of the first routine. These routines are designed as educational tools, generating exam and homework problems, and problem generating interacts.

Attachments (4)

trac_9720-random-echelonizable-matrices.patch (15.8 KB) - added by bwonderly 11 years ago.
trac_9720-random-echelonizable-matrices-v2.patch (15.8 KB) - added by bwonderly 11 years ago.
stand-alone version 2 patch, same patch with one revision
trac_9720-random-echelonizable-matrices-v3.patch (15.8 KB) - added by bwonderly 11 years ago.
stand-alone version 3 of the same patch, with import statement change and documentation revision
trac_9720-random-echelonizable-matrices-v4.patch (15.3 KB) - added by rbeezer 11 years ago.
Same as v3, but removed routines from global namespace

Download all attachments as: .zip

Change History (34)

Changed 11 years ago by bwonderly

comment:1 Changed 11 years ago by bwonderly

  • Status changed from new to needs_review

comment:2 follow-up: Changed 11 years ago by wdj

Applies fine to 4.5.2.rc0.

Two extremely minor comments off the top of my head:

  1. "Generate a matrix of a desired size and rank, over a desired field,

whose reduced row-echelon form has only whole values."

IMHO, "integral" sounds better than "whole".

  1. It seems to me that, from the point of view of the functionality,

using base_ring = ZZ returns the same result as base_ring = QQ. (I understand that over QQ the rref algorithm might be different than over ZZ, but it seems to me that for the matrices you compute in the random_echelonizable_matrix function, the rref algorithm(s) yield the same result either way. Correct?

Changed 11 years ago by bwonderly

stand-alone version 2 patch, same patch with one revision

comment:3 in reply to: ↑ 2 Changed 11 years ago by bwonderly

Replying to wdj:

Applies fine to 4.5.2.rc0.

Two extremely minor comments off the top of my head:

  1. "Generate a matrix of a desired size and rank, over a desired field,

whose reduced row-echelon form has only whole values."

IMHO, "integral" sounds better than "whole".

I agree completely and have made the change in the v2 patch.

  1. It seems to me that, from the point of view of the functionality,

using base_ring = ZZ returns the same result as base_ring = QQ. (I understand that over QQ the rref algorithm might be different than over ZZ, but it seems to me that for the matrices you compute in the random_echelonizable_matrix function, the rref algorithm(s) yield the same result either way. Correct?

Yes, the rref algorithm yields the same result with base_ring as ZZ or QQ. However, as these matrices are going to be used primarily as student example problems I think it would be better to keep the default as QQ. Although there should be a series of row operations without introducing fractions that achieves rref, a student will likely want to use fractions as they row-reduce an output matrix, and the rescale_row or add_multiple_of_row functions will complain if fractions are introduced working with a matrix over ZZ.

comment:4 Changed 11 years ago by wdj

I am ready to give this patch a positive review. However, although it aplies fine to 4.5.2.rc0, it does not pass sage -testall on a 10.6.4 mac pro. The problems seem to be in some mysterious (to me) failures in

sage -t  "local/lib/python2.6/site-packages/sagenb-0.8.2-py2.6.egg/sagenb/misc/sageinspect.py"./sage -t  "local/lib/python2.6/site-packages/sagenb-0.8.2-py2.6.egg/sagenb/misc/sageinspect.py"
-bash: sage: command not found
hera:sage-4.5.2.rc0 davidjoyner$ ./sage -t  "local/lib/python2.6/site-packages/sagenb-0.8.2-py2.6.egg/sagenb/misc/sageinspect.py"sage -t  "local/lib/python2.6/site-packages/sagenb-0.8.2-py2.6.egg/sagenb/misc/sageinspect.py"
**********************************************************************
File "/Volumes/Bay2/sagefiles2/sage-4.5.2.rc0/local/lib/python2.6/site-packages/sagenb-0.8.2-py2.6.egg/sagenb/misc/sageinspect.py", line 951:
    sage: sage_getsourcelines(matrix, True)[1]
Expected:
    34
Got:
    35

and a similar failure in

sage -t  "devel/sage/sage/misc/sageinspect.py"

I'll try investigating this using an ubuntu machine, but this seems to possibly be an issue.

comment:5 Changed 11 years ago by rbeezer

Appears to me that the test that fails is testing an actual line number of source code from the file defining the matrix constructor. Billy added an import statement at the top of the module, so the line numbers will increment by one?

Rather than patching sagenb, I'm going to do some tests - maybe adding the import of QQ to the same line as the import of ZZ will be a solution.

Rob

comment:6 Changed 11 years ago by rbeezer

  • Status changed from needs_review to needs_work

Billy,

Make a v3 patch and replace the two import statements for ZZ and QQ by the statement

from sage.rings.all import ZZ, QQ

and subsequent line numbers will return to "normal" and this very technical test should pass. Do the very complete tests

./sage -testall

overnight and then post the patch.

I've tested this change on matrix/constructor.py and the two files David has failing.

David - nice catch!

Rob

comment:7 follow-up: Changed 11 years ago by jason

In the first line of the docstring for the second function, you say:

Generate a matrix of a desired size and rank, over a desired field,

Should that say "desired ring"?

Changed 11 years ago by bwonderly

stand-alone version 3 of the same patch, with import statement change and documentation revision

comment:8 in reply to: ↑ 7 Changed 11 years ago by bwonderly

Replying to jason:

In the first line of the docstring for the second function, you say:

Generate a matrix of a desired size and rank, over a desired field,

Should that say "desired ring"?

Absolutely, I've made that change and the import statement change, and all tests passed.

comment:9 Changed 11 years ago by rbeezer

  • Status changed from needs_work to needs_review

I think this means you are ready to have the reviewing proceed, so I'll change the status to "needs review".

comment:10 Changed 11 years ago by wdj

  • Status changed from needs_review to positive_review

The latest patch applies fine to 4.5.2.rc0 and passes sage -testall on a 10.6.4 mac pro.

This is a well-documented addition and I definitely will use it teaching linear algebra this semester. Thanks for coding this up!

comment:11 Changed 11 years ago by mpatel

  • Reviewers set to David Joyner

comment:12 Changed 11 years ago by bwonderly

Thanks everyone for the suggestions and the expeditious review!

Release manager: apply only v3 patch.

comment:13 follow-up: Changed 11 years ago by mhansen

  • Status changed from positive_review to needs_info

I think that these should really just be options to the random_matrix function so that we don't have a ton of random_*_matrix commands floating around in the global namespace.

comment:14 in reply to: ↑ 13 Changed 11 years ago by wdj

Replying to mhansen:

I think that these should really just be options to the random_matrix function so that we don't have a ton of random_*_matrix commands floating around in the global namespace.

Though this is logical, I personally vote -1 as it will be somewhat harder to use for those who need it (teachers not necessarily expert in Sage but needing it for a quick computation for an example or 2 in a lecture note).

In any case, I hope this will be approved as I am teaching this *right now*:-)

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

There won't be tons, just four I think. ;-) But I agree entirely.

Would you pass some sort of selector in *args, then make these methods of some class of matrices? How would the documentation be immediately or easily accessible? Is there a model we can follow someplace else in Sage?

If you'd be able to suggest a course of action, I can work with Billy to make this happen. He's finished posting all his routines (there aren't any more planned) and classes begin Monday, so it'd be nice to get this going quickly so he can wrap up his summer project.

Thanks again, I'd had the same reservations about adding to the global namespace, but hadn't hit on this option.

Rob

comment:16 Changed 11 years ago by rbeezer

I agree with David's comments about documentation - maybe we can make that happen smoothly and logically, but its not coming to me right at the moment.

comment:17 in reply to: ↑ 15 Changed 11 years ago by mhansen

Replying to rbeezer:

Would you pass some sort of selector in *args, then make these methods of some class of matrices? How would the documentation be immediately or easily accessible? Is there a model we can follow someplace else in Sage?

You can leave the functions as they are -- just don't import them into the global namespace. Then, if you do,

sage: a = random_matrix(QQ, 3, 3, rref=True)
sage: b = random_matrix(QQ, 3, 3, echelonizable=True)

which just delegate to the appropriate function. You can add a reference to those functions in the docstring of random_matrix. Also, the documentation is not clear on why there is special casing for ZZ and QQ, and that these methods don't work for inexact rings. Although, you could argue that if you have one of these matrices over ZZ you could just convert all the entries to RR and things "should" be fine.

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

Mike -

OK, that makes sense - thanks.

We also have "diagonalizable", "unimodular" and "subspaceable", so I think something like a single keyword type/category/class/method/algorithm (I don't really like any of those too much) that defaults to the current "randomize" behavior would be better. Is "algorithm" the policy these days for this type of thing? Some constructors must be square so we would have to check for that first. (And we can address the ZZ, QQ, inexact situation.)

Thanks for the suggestion and quick help.

David - I think I can make the HTML docs work well, and can include the necessary import/qualified statement in the tab-completion documentation to make the notebook/command-line docs relatively easy to access. We'd include at least one full example in the docs for random_matrix() so it could be discovered that way. Does that sound OK?

Billy - I'll try to set things up to make current patch work. It won't be too hard then for you to adjust the other two that are outstanding. Sound OK?

Rob

comment:19 in reply to: ↑ 18 Changed 11 years ago by wdj

Replying to rbeezer:

Mike -

...

David - I think I can make the HTML docs work well, and can include the necessary import/qualified statement in the tab-completion documentation to make the notebook/command-line docs relatively easy to access. We'd include at least one full example in the docs for random_matrix() so it could be discovered that way. Does that sound OK?

Sounds good - thanks Rob (and Mike)!!

Rob

comment:20 Changed 11 years ago by rbeezer

  • Status changed from needs_info to needs_work

comment:21 follow-up: Changed 11 years ago by jason

To take care of the namespace issue, what about making it work like graphs does? In other words, "random_matrix" behaves like it always has, and "random_matrix.echelonizable(...)", "random_matrix.unimodular()", etc., do the specialized functions?

I'm a slight -1 on making random_matrix take a ton of options, a lot of which may be mutually exclusive. For example, if I ask for a random echelonizable matrix over ZZ, with a specific range of entries, will it work?

Changed 11 years ago by rbeezer

Same as v3, but removed routines from global namespace

comment:22 Changed 11 years ago by rbeezer

v4 patch is identical to v3, except the two new routines are not imported into the global namespace, and therefore two import commands are needed in the doctests.

sage/matrix/constructor.py passes randomized testing (-randorder) with these changes. Full testing later. Upcoming patch will have random_matrix() delegate to these two routines.

Billy's name should still be on this patch as the author.

Rob

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

Replying to jason:

To take care of the namespace issue, what about making it work like graphs does? In other words, "random_matrix" behaves like it always has, and "random_matrix.echelonizable(...)", "random_matrix.unimodular()", etc., do the specialized functions?

I'm a slight -1 on making random_matrix take a ton of options, a lot of which may be mutually exclusive. For example, if I ask for a random echelonizable matrix over ZZ, with a specific range of entries, will it work?

Right now I'm thinking:

random_matrix(RR, 6, 4, algorithm='randomize')

random_matrix(ZZ, 6, 4, algorithm='echelon_form')

random_matrix(ZZ, 3, 4, algorithm='echelonizable')

random_matrix(ZZ, 8, 8, algorithm='diagonalizable')

etc. random_matrix() would be a big switch on the value of algorithm. Default would be 'randomize' and preserve current behavior. random_matrix() would throw errors for "wrong" rings, or "wrong" shapes.

random_matrix() would have one good example of each type, with link to actual routine's documentation for PDF & HTL version. For notebook or CL docs, the documentation would say "use sage.constructor.random_echelonizable_matrix?" for more detailed documentation right after the example (not tested).

random_matrix() already takes lots of options - anything the randomize function of the entry type accepts. I think the new functions only accept upper_bound as an option, as a type of what Billy calls "size control". Currently, the possibilities for arguments is not handled very well:

sage: random_matrix(QQ, 3, 4, num_bound = 4, den_bound = 10)
[-3/8 -3/5    1 -4/7]
[ 3/2  2/3   -2 -1/2]
[-1/8  1/2  1/8 -3/8]
sage: random_matrix(ZZ, 3, 4, num_bound = 4, den_bound = 10)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/sage/dev/devel/sage-main/<ipython console> in <module>()

/sage/dev/local/lib/python2.6/site-packages/sage/matrix/constructor.pyc in random_matrix(R, nrows, ncols, sparse, density, *args, **kwds)
    829         A.randomize(density=float(1), nonzero=False, *args, **kwds)
    830     else:
--> 831         A.randomize(density=density, nonzero=True, *args, **kwds)
    832     return A
    833

/sage/dev/local/lib/python2.6/site-packages/sage/matrix/matrix_integer_dense.so in sage.matrix.matrix_integer_dense.Matrix_integer_dense.randomize (sage/matrix/matrix_integer_dense.c:23941)()

TypeError: randomize() got an unexpected keyword argument 'num_bound'

I'm -1 to implementing the whole graphs-dot infrastructure for just five or six functions right as Billy is trying to wrap this up. (And possibly having to deprecate any current behavior.) I do want to (but have not found the time yet) to implement the dot-syntax for groups.

Just a thought - we could implement a whole random-dot hierarchy: matrices, primes, graphs,....

comment:24 follow-up: Changed 11 years ago by jason

The algorithm keyword seems natural enough for me. What I was opposed to was 5 different True/False? keyword options, each mutually exclusive for the others.

comment:25 in reply to: ↑ 24 Changed 11 years ago by rbeezer

Replying to jason:

The algorithm keyword seems natural enough for me. What I was opposed to was 5 different True/False? keyword options, each mutually exclusive for the others.

Good - I didn't want that either. I'm going to start on the above shortly.

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

  • Status changed from needs_work to needs_review

Into the random_matrix routine and I've never been happy with the documentation, and I may even change the code now that I've dipped into it. So I'm going to do that work on a new ticket along with allowing for integrating the new constructions. See #9803.

That means that the v4 patch makes this ready to go. It'll be left hidden until #9803 is done, but at least David J can import it as needed until then.

So if Billy or David want to check-off on my changes from v3 to v4 (undid changes in all.py and added two imports to doctests) then this can go to positive review. I'll add interested parties to #9803 once I have a patch up, so no need to add yourself yet unless you have more comments.

This also allows Billy to be sole author on this.

comment:27 in reply to: ↑ 26 Changed 11 years ago by wdj

Replying to rbeezer:

...

So if Billy or David want to check-off on my changes from v3 to v4 (undid changes in all.py and added two imports to doctests) then this can go to positive review. I'll add interested parties to #9803 once I have a patch up, so no need to add yourself yet unless you have more comments.

This looks good to me (I even tested it again for safety's sake:-).

This also allows Billy to be sole author on this.

comment:28 Changed 11 years ago by rbeezer

  • Status changed from needs_review to positive_review

Thanks, David. I'm going to move this back to positive review. Patch up at #9803 to reflect discussion above.

Release manager

Apply only the v4 patch and please merge with #9803 once it is ready - the calling syntax changes, so both tickets should go in together.

comment:29 Changed 11 years ago by bwonderly

Release Manager

#9720, #9803, #9802, #9754 is each dependent on the predecessor, merge in this order.

comment:30 Changed 11 years ago by mpatel

  • Merged in set to sage-4.6.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.