#11358: matrix multiplication over ZZ sometimes gives incorrect results
------------------------------+---------------------------------------------
Reporter: tomc | Owner:
Type: defect | Status: needs_work
Priority: critical | Milestone: sage-4.7.1
Component: linear algebra | Keywords: matrix multiplication,
multi-modular, integers, ZZ
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
------------------------------+---------------------------------------------
Comment(by tomc):
Replying to [comment:14 burcin]:
> Multi precision integers are needed for the lifting step. One of the
reasons to use a multi-modular algorithm is to take advantage of fast
arithmetic implemented in hardware. This requires that the modulus is
small enough to fit in a word size.
I agree that things will slow down if we ever raise self._ubound to be
larger than a machine word: my question was whether anything would
actually break. But in any case, since the MultiModularBasis class is
explicitly documented as:
{{{
"""
This class stores a list of machine-sized prime numbers...
"""
}}}
we should not allow the code to raise self._ubound. Thus we should raise
an error if we repeatedly fail to choose a new random prime. As
discussed, we will need to handle this error in several other places in
Sage.
Note that the situation we are discussing is very unlikely to ever occur
in practice, as the default values of _lbound and _ubound are repectively
2**10 and 2**15 and there are many primes in between 2**10 and 2**15. But
in theory someone could do:
{{{
sage: mm = MultiModularBasis(lbound=4,ubound=6,...)
}}}
or something equally silly, and then the multi-modular code would quickly
run out of primes.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11358#comment:15>
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.
