#10733: Faster echelon form code for matrix_modn_sparse
--------------------------------+-------------------------------------------
Reporter: tornaria | Owner: was
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-4.7
Component: linear algebra | Keywords:
Author: Gonzalo Tornaria | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Changes (by tornaria):
* status: needs_review => positive_review
Comment:
I reviewed the new patch and ran the test suite, which passes for me as
well.
The problematic method was {{{Matrix_modn_sparse.set_block_unsafe(...,
Matrix_modn_dense m)}}} which is meant to set a block of a sparse matrix
given by a dense matrix. But for mod 2, the dense matrices are implemented
by a different class ({{{Matrix_mod2_dense}}}) so calls to
{{{set_block_unsafe}}} will fail. What the reviewer patch does is to
factor out a common superclass for both {{{Matrix_mod_dense}}} which can
be used in the implementation of {{{set_block_unsafe}}}.
I noticed that computing echelon form for a sparse mod2 matrix is much
slower than converting the matrix to dense and using echelon form (which
uses M4RI and is quite fast). Thus, it could make sense to reimplement
sparse mod2 echelon form via conversion to dense. However, note that
conversion from mod2 dense to mod2 sparse is quite slow currently.
In spite of the above comment, I'm giving positive review to patch 4 based
on:
- the code works properly for mod2 sparse matrices, so no functionality
regression.
- it runs definitely faster than what we had before for sparse matrices,
so no performance regression.
Since this ticket gives significant improvements for larger modulus, it's
important that we merge it even if it's not the best we could do for the
modulus 2.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10733#comment:13>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
