#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: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.
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.
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11358#comment:13>
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.
