#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:
----------------------------------+-----------------------------------------
Changes (by Bouillaguet):
* status: positive_review => needs_work
Comment:
There are cases where the patch is in fact a huge regression !
I ran the following test :
{{{
sage: sage: for i in range(1,6):
M = random_matrix( Integers(p), 75*i )
time d = M.det()
}}}
with ``p = next_prime( factorial(20) )`` and ``sage: p = next_prime(
factorial(21) )``
Before patch:
{{{
# 20!
Time: CPU 0.10 s, Wall: 0.10 s
Time: CPU 0.56 s, Wall: 0.55 s
Time: CPU 1.56 s, Wall: 1.51 s
Time: CPU 3.62 s, Wall: 3.10 s
Time: CPU 6.46 s, Wall: 5.26 s
# 21!
Time: CPU 0.17 s, Wall: 0.17 s
Time: CPU 0.61 s, Wall: 0.59 s
Time: CPU 1.72 s, Wall: 1.67 s
Time: CPU 3.92 s, Wall: 3.36 s
Time: CPU 6.85 s, Wall: 5.63 s
}}}
After patch:
{{{
# 20!
Time: CPU 0.11 s, Wall: 0.11 s
Time: CPU 0.51 s, Wall: 0.51 s
Time: CPU 1.17 s, Wall: 1.17 s
Time: CPU 2.15 s, Wall: 2.15 s
Time: CPU 3.43 s, Wall: 3.43 s # this is cool
# 21!
Time: CPU 0.17 s, Wall: 0.17 s
Time: CPU 0.65 s, Wall: 0.65 s
Time: CPU 1.77 s, Wall: 1.77 s
Time: CPU 4.06 s, Wall: 4.06 s
Time: CPU 36.89 s, Wall: 36.89 s # problem here
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14007#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 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.
