#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:
------------------------------+---------------------------------------------
Something is wrong with the multi-modular matrix multiplication code for
matrices over ZZ. At random, and infrequently, it gives incorrect
results. For example, the following code chooses random 3x2 and 2x10
integer matrices and multiplies them together using the multi-modular
algorithm. It then does the same multiplication 100 more times, checks
that the answer is always the same, and if not raises an exception:
{{{
sage: for n in range(2000):
....: A = MatrixSpace(ZZ,3,2).random_element()
....: B = MatrixSpace(ZZ,2,10).random_element()
....: try_once = A._multiply_multi_modular(B)
....: for k in range(100):
....: try_again = A._multiply_multi_modular(B)
....: if try_once != try_again:
....: print "="*60
....: print "n = %s, k = %s"%(n,k)
....: print "A = "
....: print A
....: print "B ="
....: print B
....: print "first attempt = "
....: print try_once
....: print "k-th retry = "
....: print try_again
....: raise RuntimeError
....:
}}}
This fails with very high probability (on Sage 4.6.2 under OS X, built
from source) with output such as:
{{{
============================================================
n = 27, k = 43
A =
[-1 0]
[ 1 0]
[ 0 1]
B =
[ -2 1 -1 0 0 -1 -1 3 -1 -1]
[ 1 1 -116 3 0 -1 -1 0 -1 0]
first attempt =
[ 2 -1 1 0 0 1 1 -3 1 1]
[ -2 1 -1 0 0 -1 -1 3 -1 -1]
[ 1 1 -116 3 0 -1 -1 0 -1 0]
k-th retry =
[ 2 1102 1 0 0 1 1 1100 1 1]
[1101 1 1102 0 0 1102 1102 3 1102 1102]
[ 1 1 987 3 0 1102 1102 0 1102 0]
---------------------------------------------------------------------------
RuntimeError [...]
}}}
Note that the two candidates for the matrix product here are congruent
modulo 1103, which is prime. If you rerun the code with verbose logging,
using set_verbose(2), then every time it fails the two candidates for the
matrix product are congruent modulo the prime being used in the multi-
modular algorithm. Thus I suspect that the Chinese Remainder Theorem code
in sage/ext/multi_modular.pyx is not handling a corner case properly.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11358>
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.
