#4968: implement fast linear algebra modulo n < 2^31
----------------------------------+-----------------------------------------
Reporter: malb | Owner: was
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-wishlist
Component: linear algebra | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #10281 | Stopgaps:
----------------------------------+-----------------------------------------
Changes (by malb):
* status: needs_review => needs_work
Comment:
'''32-bit vs 64-bit'''
* I think there is a bit of confusion about 32-bit vs. 64-bit in the
patch, or at least I am confused. If I understand correctly, then
{{{ctypedef unsigned long uint_fast64_t}}} is used to define the data type
of the matrix. However, {{{unsigned long}}} is not necessarily 64-bit, on
32-bit machines it may be 32-bit. Arithmetic uses {{{long long}}} which is
at least 64-bit. So either the datatype should not mention 64 bits or
should be moved over to e.g. {{{uint64_t}}} or {{{unsigned long long}}}
(which doesn't exist in older C++ standards FWIW). Once this is fixed
there seem to be a few places like: "Reduce the integer matrix modulo a
positive machine size integer." and "stored as a 64-bit unsigned int"
which might need adapting too.
* I am not sure about this code:
{{{
#!python
if use_32bit_type(p):
raise RuntimeError, "BUG: p (=%s) is too small to use this matrix
type"%p
}}}
Why raise an error? Of course, the !LinBox matrices take care of that by
default, I am just confused by this. Also, this seems to contradict with
"If the prime is small enough to fit in a byte" later.
* I assume this {{{long long}}} vs {{{unsigned long long}}} is the reason
for restricting the modulus to 2^31^?
'''mod_int vs. mod_int_uint64'''
* I think Robert's merge introduced a bug in pickling. We are at version
10 of pickling for {{{Matrix_modn_dense}}} but William started counting at
zero again for his new type. Now that we're back to the old type, we
shouldn't check for {{{version == 0}}}.
'''Other stuff'''
* "TODO: should free up memory allocated so far -- this would leak
otherwise, in exactly a situation where a *lot* leaks" Shouldn't this be
fixed?
* Of course, far from mandatory but couldn't we -- while we are at it --
not also fix those {{{raise OverflowError, string}}} to read {{{raise
OverflowError(string)}}} which is Python3 style (?)
* performance: it seems picking a bigger Strassen cutoff would be quite
beneficial:
{{{
sage: A = random_matrix(GF(previous_prime(2^24)),1000,1000)
sage: %time A*A
CPU times: user 2.67 s, sys: 0.00 s, total: 2.68 s
Wall time: 2.69 s
1000 x 1000 dense matrix over Finite Field of size 16777213
sage: %time A._multiply_strassen(A,100)
CPU times: user 1.12 s, sys: 0.00 s, total: 1.12 s
Wall time: 1.13 s
1000 x 1000 dense matrix over Finite Field of size 16777213
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4968#comment:17>
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.
