#14007: When computing determinant over GF(p), don't lift to ZZ
----------------------------------+-----------------------------------------
Reporter: jdemeyer | Owner: jason, was
Type: enhancement | Status: needs_work
Priority: blocker | Milestone: sage-5.7
Component: linear algebra | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: Charles Bouillaguet
Authors: Jeroen Demeyer | Merged in:
Dependencies: | Stopgaps:
----------------------------------+-----------------------------------------
Comment (by Bouillaguet):
Sounds good. I don't know how to detect the word size inside sage (?). It
amazes me that moving from "less than 64 bits" to "more than 64 bits"
actually speeds up the process instead of slowing it down in the integer
case...
I also checked that the corresponding PARI routine ({{{Flm_det_sp_OK}}} in
{{{src/basemath/linalg1.c}}}) does not require the characteristic of the
ring to be prime. The same procedure in PARI deals with determinants in
ZZ/6ZZ and ZZ/11ZZ. So, in theory, we could use PARI for all kinds of
{{{IntegerMod(...)}}}, with a clear benefit when p is small enough to fit
in a machine word. I tried to get rid of the prime limitation but failed
with an error I did not understand... Jeroen, could you try?
Also, note that the PARI implementation is rather naïve : is performs a
simple gaussian elimination (no strassen, no fancy stuff). A longer-term
objective would be to let FFLAS do this.
Also, another longer-term objective would ben when the modulus is too
large, to use the chinese reminder theorem to work only modulo small
primes (this can also be done modulo the integers). But this would
require PARI to handle the non-prime cases.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14007#comment:11>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
