#11358: matrix multiplication over ZZ sometimes gives incorrect results
------------------------------+---------------------------------------------
Reporter: tomc | Owner: jason, was
Type: defect | Status: new
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 dsm):
I think I've got it.
This seems to happen iff a random prime happens to be chosen twice. For
example, if you modify _extend_moduli_to_height_c to always reuse a prime
if more than one is needed, this always happens. The same bug seems to
exist in _extend_moduli_to_count as well.
The problem seems to be that in _new_random_prime, there's a test which
doesn't do what it's trying to do:
{{{
cdef mod_int _new_random_prime(self):
# choose a new random prime
cdef Py_ssize_t i
cdef mod_int p
while True:
p = random_prime(self._u_bound, lbound =self._l_bound)
for i in range(self.n):
if p == self.moduli[i]:
break
else:
return p
}}}
IIUC, the "for i in range(self.n)" loop is attempting to avoid the problem
of repeated primes, but this only works if p is added to self.moduli
immediately after it's returned. In the case of
_extend_moduli_to_height_c, this isn't true; the addition is delayed until
a later extend_with_primes call, so the above check decides that the prime
isn't reused, we get repeated moduli, and the multiplication breaks.
Or even more obviously:
{{{
sage: from sage.ext.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base(1)
sage: mm._extend_moduli_to_count(1000)
1000
sage: len(mm), len(set(mm))
(1000, 843)
}}}
ISTM either we can remove the check-for-duplicate code from
_new_random_prime and do it externally, or we can add an argument and pass
it the "accumulated" primes as we build them elsewhere so it can avoid
duplicates there too. I prefer the first. Should I work up a patch?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11358#comment:6>
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.
