Opened 12 years ago

Last modified 8 years ago

#10734 needs_work enhancement

Improve matrix_modn_sparse methods for converting to dense and taking submatrices

Reported by: Gonzalo Tornaría Owned by: William Stein
Priority: major Milestone: sage-6.6
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Gonzalo Tornaria Reviewers: William Stein, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: public/matrix/improve_modn_sparse_methods-10734 (Commits, GitHub, GitLab) Commit: d3f8b5fb5b220fcba8874484f6d09700409159b6
Dependencies: #17837 Stopgaps:

Status badges

Description

Here I'll post some improvements that are needed for #10733 but are of independent interest.

Attachments (4)

trac_10734.dense_matrix_and_submatrix (4.5 KB) - added by Gonzalo Tornaría 11 years ago.
For matrix_modn_sparse: implement optimized versions of submatrix(), dense_matrix(), add methods dense_submatrix() and set_block_unsafe()
trac_10734.02-documentation (4.9 KB) - added by Gonzalo Tornaría 11 years ago.
Add documentation for the functions added in #10734
trac_10734.03-referee_refactor_to_support_p2.patch (9.0 KB) - added by Gonzalo Tornaría 11 years ago.
refactor code to support p=2 case (part 1)
trac_10734-dense_matrix_and_submatrix-folded.patch (12.1 KB) - added by David Loeffler 11 years ago.
Apply only this patch. Patch against 5.0.beta7

Download all attachments as: .zip

Change History (27)

comment:1 Changed 12 years ago by Gonzalo Tornaría

Status: newneeds_review

comment:2 Changed 12 years ago by William Stein

Status: needs_reviewneeds_work

This ticket introduces a bunch of new functions, but doesn't include any documentation or doctests for them.

comment:3 Changed 12 years ago by Gonzalo Tornaría

Status: needs_workneeds_review

The new patch adds documentation to all the functions created in the first patch.

comment:4 Changed 12 years ago by William Stein

Status: needs_reviewpositive_review

Great!

comment:5 Changed 12 years ago by Jeroen Demeyer

Milestone: sage-4.7
Reviewers: William Stein

comment:6 Changed 11 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

Patches should be created using hg export tip and not hg diff or any other method. Also make sure you have a file $HOME/.hgrc as explained in the developer's manual.

comment:7 in reply to:  6 Changed 11 years ago by Gonzalo Tornaría

Replying to jdemeyer:

Patches should be created using hg export tip and not hg diff or any other method. Also make sure you have a file $HOME/.hgrc as explained in the developer's manual.

Is it just this

# User Gonzalo Tornaria <tornaria@cmat.edu.uy>

what the patches are missing?

This is a misfeature of mercurial (queues), because it doesn't set the user by default in the patches. Very silly.

Do you need me to reupload all the patches again, or can you just use

-u "Gonzalo Tornaria <tornaria@cmat.edu.uy>"

as an option when you run hg import? Reuploading 7 files to trac gets boring (is there an easier way to a batch upload to trac? from the command line?).

[as a general comment; I'd prefer if the requirements are stated in terms of what the patches need to include, rather than dictating how one must use mercurial -- I find mercurial inconvenient to use without using queues, because the history cannot be rewritten and I don't know how to effectively use branches -- I've been spoiled by git, I guess]

Changed 11 years ago by Gonzalo Tornaría

For matrix_modn_sparse: implement optimized versions of submatrix(), dense_matrix(), add methods dense_submatrix() and set_block_unsafe()

Changed 11 years ago by Gonzalo Tornaría

Attachment: trac_10734.02-documentation added

Add documentation for the functions added in #10734

Changed 11 years ago by Gonzalo Tornaría

refactor code to support p=2 case (part 1)

comment:8 Changed 11 years ago by Gonzalo Tornaría

Status: needs_workneeds_review

I've reuploaded the two patches (hopefully) with the right format (username and date).

Also, I moved part of the referee patch in #10733 here, otherwise some doctests would fail until that ticket is merged.

There's no new code at all, so I assume the positive review is still valid.

comment:9 Changed 11 years ago by Gonzalo Tornaría

apply trac_10734.dense_matrix_and_submatrix, trac_10734.02-documentation, trac_10734.03-referee_refactor_to_support_p2.patch

comment:10 Changed 11 years ago by Frédéric Chapoton

Maybe you should add .patch at the end of the names of your patches. Otherwise they are not recognised as such, it seems.

Changed 11 years ago by David Loeffler

Apply only this patch. Patch against 5.0.beta7

comment:11 Changed 11 years ago by David Loeffler

I qfolded Gonzalo's patches into a single patch, and made sure it has ".patch" at the end of its name, as Frederic suggests. But with this (or, equivalently, Gonzalo's original three patches) installed I get some doctest failures in sage/matrix/matrix_modn_sparse -- any ideas what's causing that?

comment:12 Changed 11 years ago by David Loeffler

Status: needs_reviewneeds_work

Looks like the patchbot is getting the same failures, under both 4.8 and 5.0.beta7. I'm afraid that's "needs work", then. Here's an example of the kind of error that's coming up:

sage -t  -force_lib devel/sage-10734/sage/matrix/matrix_modn_sparse.pyx
**********************************************************************
File "/Users/patchbot/sage-4.8/devel/sage-10734/sage/matrix/matrix_modn_sparse.pyx", line 635:
    sage: A.dense_submatrix(24,24,3,3)
Exception raised:
    Traceback (most recent call last):
      File "/Users/patchbot/sage-4.8/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/patchbot/sage-4.8/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/patchbot/sage-4.8/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_10[4]>", line 1, in <module>
        A.dense_submatrix(Integer(24),Integer(24),Integer(3),Integer(3))###line 635:
    sage: A.dense_submatrix(24,24,3,3)
      File "matrix_modn_sparse.pyx", line 655, in sage.matrix.matrix_modn_sparse.Matrix_modn_sparse.dense_submatrix (sage/matrix/matrix_modn_sparse.c:11628)
        M = self.new_matrix(nrows, ncols, sparse=False)
    TypeError: Cannot convert sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float to sage.matrix.matrix_mod_dense.Matrix_mod_dense
**********************************************************************

comment:13 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:14 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:15 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:16 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:17 Changed 8 years ago by Travis Scrimshaw

Branch: public/matrix/improve_modn_sparse_methods-10734
Commit: 8bc6935c6085a2f7de0e227f2c961d4e875df181
Reviewers: William SteinWilliam Stein, Travis Scrimshaw
Status: needs_workneeds_review

Git branch and also has the fixes for the sparse conversion by making the matrix_modn_dense_template inherit from matrix_mod_dense


New commits:

c0a74b9#10734: Matrix_modn_sparse speed improvements
8bc6935Made modn dense template inherit from mod_dense.

comment:18 Changed 8 years ago by Frédéric Chapoton

Status: needs_reviewneeds_work

needs rebase

comment:19 Changed 8 years ago by git

Commit: 8bc6935c6085a2f7de0e227f2c961d4e875df181d3f8b5fb5b220fcba8874484f6d09700409159b6

Branch pushed to git repo; I updated commit sha1. New commits:

d3f8b5fMerge branch 'public/matrix/improve_modn_sparse_methods-10734' of trac.sagemath.org:sage into public/matrix/improve_modn_sparse_methods-10734

comment:20 Changed 8 years ago by Travis Scrimshaw

Status: needs_workneeds_review

Rebased to 6.4.rc1.

comment:21 Changed 8 years ago by Vincent Delecroix

Status: needs_reviewneeds_info

Hello,

What is the purpose of introducing the class Matrix_mod_dense?

Vincent

comment:22 Changed 8 years ago by Vincent Delecroix

Ticket #17837 proposes to remove matrix_modn_dense (it is unused since a long time and much slower than matrix_modn_dense_float or matrix_modn_dense_double using LinBox?). Is there anybody working on this ticket that can say something about it? Otherwise I will put #17837 in positive review (and consequently this one in needs work).

Vincent

comment:23 Changed 8 years ago by Jeroen Demeyer

Dependencies: #17837
Milestone: sage-6.4sage-6.6
Status: needs_infoneeds_work
Note: See TracTickets for help on using tickets.