#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 burcin):
Replying to [comment:13 tomc]:
> Replying to [comment:12 burcin]:
>
> > I suggest raising an error instead of increasing `_ubound`. The upper
bound is usually set so that the primes fit in a single machine word. A
lot of things would break if this changed without notice.
>
> If we do raise an error then it should be caught before it propagates up
to the user. For instance, it should not be that if A and B are integer
matrices then evaluating A*B can sometimes cause an exception because the
multi-modular matrix multiplication algorithm ran out of primes: in this
case we should catch the exception and evaluate A*B using a different
algorithm.
This is better than trying to handle it magically in the
`MultiModularBasis` class.
> Is it really the case that raising self._ubound would cause things to
break? I thought from looking at the multi-modular code that it all used
mpz_t types from GMP, and that these would automatically increase their
allocated memory as necessary.
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. For linear algebra, the dimensions of
the matrix also come into play. Ideally you should reduce only once for
each row*column multiplication.
> The multi-modular code is used in five places: dense matrix
multiplication over ZZ; dense matrix multiplication over cyclotomics;
dense matrix multiplication over QQ (although only in the rational
reconstruction routines _lift_crt_rr() and _lift_crt_rr_with_lcm(), which
I think are dead code); echelon form calculations over cyclotomics; and
characteristic polynomial calculations over cyclotomics. If we decide to
raise an error if the multi-modular code runs out of primes then we will
need to catch this error and handle it appropriately in all five places.
You cannot assume that the only users of the code are in the Sage library.
This class is designed to be an abstraction that makes it easy to
implement multi modular algorithms.
Perhaps we can verify that this error will never occur in these places
through some theoretical argument. It is highly unlikely that we will
always keep choosing the same random prime.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11358#comment:14>
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.
