#15104: Special case modn_dense matrix operations to improve performance
-------------------------------------+-------------------------------------
Reporter: nbruin | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.2
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: Nils Bruin | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/nbruin/ticket/15104 | a908e28159a544ca33f03dcbf0e8def3cfe9a60e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
In the ticket description, you say: "taking a transpose of a modn_dense
matrix of smallish size is much more expensive than constructing the right
kernel, '''because the method is just a generic implementation.'''"
In contrast, I believe that there ''should'' be a generic implementation
of the transpose, or at least there should be some generic helper methods
for creating the transposed matrix.
For example, it should make sense to have a method of a matrix space
returning the transposed matrix space, and this method should perhaps even
be a cached method. When using this helper in all custom implementations
of `.transpose()`, then the time to create the transposed matrix' parent
could be reduced.
Moreover, all matrices are supposed to provide fast `set/get_unsafe()`
methods. Are you really sure that a generic implementation relying on
these fast "unsafe" methods would be slower than a custom implementation
such as the one of `Matrix_modn_dense` that uses the underlying data
structure directly, rather than using `set/get_unsafe`:
{{{
#!python
def transpose(self):
...
for i from 0 <= i < ncols:
for j from 0 <= j < nrows:
M._entries[j+i*nrows] = self._entries[i+j*ncols]
}}}
And is this really the correct thing to do? Namely, in the unsafe set/get
method of `Matrix_modn_dense_float`, the operations are done on the
attribute `._matrix`, not `._entries`. If I understand correctly,
`._matrix` is arranged in rows, whereas `._entries` is the same chunk of
memory, but not separated in rows. But then, wouldn't it be faster to use
`._matrix` as long as one stays in the same row (which in the above loop
over `j` is the case for `M`?
Regardless whether we create a fully fledged generic implementation of
`.transpose()` or just provide new helper methods: We need to address the
following custom `.transpose()` methods:
{{{
matrix/matrix_integer_dense.pyx:4770: def transpose(self):
matrix/matrix_mod2_dense.pyx:1430: def transpose(self):
matrix/matrix_double_dense.pyx:2242: def transpose(self):
matrix/matrix_sparse.pyx:365: def transpose(self):
matrix/matrix_rational_dense.pyx:2356: def transpose(self):
matrix/matrix_modn_sparse.pyx:684: def transpose(self):
matrix/matrix_dense.pyx:131: def transpose(self):
modules/free_module_element.pyx:1119: def transpose(self):
misc/functional.py:1746:def transpose(x):
misc/table.py:366: def transpose(self):
combinat/alternating_sign_matrix.py:311: def transpose(self):
libs/ntl/ntl_mat_GF2E.pyx:538: def transpose(ntl_mat_GF2E self):
libs/ntl/ntl_mat_GF2.pyx:559: def transpose(ntl_mat_GF2 self):
matroids/lean_matrix.pyx:332: cdef LeanMatrix transpose(self):
matroids/lean_matrix.pyx:695: cdef LeanMatrix transpose(self):
matroids/lean_matrix.pyx:1114: cdef LeanMatrix transpose(self):
matroids/lean_matrix.pyx:1734: cdef LeanMatrix transpose(self):
matroids/lean_matrix.pyx:2250: cdef LeanMatrix transpose(self):
matroids/lean_matrix.pyx:2706: cdef LeanMatrix transpose(self):
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/15104#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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
