#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 jdemeyer):
I get different timings, the patch always seems to help.
I used the script
{{{
def dettest(k):
print "Testing", k
for s in [50,75..300]:
M = random_matrix(k, s)
print "Size%4i"%s,
time d = M.det()
dettest(Integers(2432902008176640029))
dettest(Integers(51090942171709440031))
}}}
Without patch:
{{{
Testing Ring of integers modulo 2432902008176640029
Size 50 Time: CPU 1.43 s, Wall: 1.43 s
Size 75 Time: CPU 0.28 s, Wall: 0.43 s
Size 100 Time: CPU 0.33 s, Wall: 0.33 s
Size 125 Time: CPU 0.51 s, Wall: 0.51 s
Size 150 Time: CPU 0.88 s, Wall: 0.88 s
Size 175 Time: CPU 1.17 s, Wall: 1.17 s
Size 200 Time: CPU 1.64 s, Wall: 1.64 s
Size 225 Time: CPU 2.19 s, Wall: 2.19 s
Size 250 Time: CPU 2.90 s, Wall: 2.91 s
Size 275 Time: CPU 3.82 s, Wall: 3.83 s
Size 300 Time: CPU 4.50 s, Wall: 4.50 s
Testing Ring of integers modulo 51090942171709440031
Size 50 Time: CPU 1.53 s, Wall: 1.53 s
Size 75 Time: CPU 0.18 s, Wall: 0.18 s
Size 100 Time: CPU 0.34 s, Wall: 0.34 s
Size 125 Time: CPU 0.54 s, Wall: 0.53 s
Size 150 Time: CPU 0.88 s, Wall: 0.88 s
Size 175 Time: CPU 1.28 s, Wall: 1.28 s
Size 200 Time: CPU 1.71 s, Wall: 1.72 s
Size 225 Time: CPU 2.29 s, Wall: 2.33 s
Size 250 Time: CPU 2.99 s, Wall: 3.00 s
Size 275 Time: CPU 3.83 s, Wall: 3.84 s
Size 300 Time: CPU 4.67 s, Wall: 4.67 s
}}}
With patch:
{{{
Testing Ring of integers modulo 2432902008176640029
Size 50 Time: CPU 0.09 s, Wall: 0.09 s
Size 75 Time: CPU 0.20 s, Wall: 0.20 s
Size 100 Time: CPU 0.36 s, Wall: 0.36 s
Size 125 Time: CPU 0.58 s, Wall: 0.61 s
Size 150 Time: CPU 0.92 s, Wall: 0.92 s
Size 175 Time: CPU 1.26 s, Wall: 1.26 s
Size 200 Time: CPU 1.64 s, Wall: 1.64 s
Size 225 Time: CPU 2.06 s, Wall: 2.05 s
Size 250 Time: CPU 2.62 s, Wall: 2.62 s
Size 275 Time: CPU 3.19 s, Wall: 3.19 s
Size 300 Time: CPU 3.73 s, Wall: 3.73 s
Testing Ring of integers modulo 51090942171709440031
Size 50 Time: CPU 0.10 s, Wall: 0.10 s
Size 75 Time: CPU 0.32 s, Wall: 0.32 s
Size 100 Time: CPU 0.47 s, Wall: 0.47 s
Size 125 Time: CPU 0.86 s, Wall: 0.86 s
Size 150 Time: CPU 1.29 s, Wall: 1.29 s
Size 175 Time: CPU 1.82 s, Wall: 1.82 s
Size 200 Time: CPU 2.46 s, Wall: 2.46 s
Size 225 Time: CPU 3.34 s, Wall: 3.36 s
Size 250 Time: CPU 4.48 s, Wall: 4.48 s
Size 275 Time: CPU 5.85 s, Wall: 5.85 s
Size 300 Time: CPU 7.71 s, Wall: 7.72 s
}}}
This seems to suggest that improvements are needed in the integer
`determinant()` function.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14007#comment:15>
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.
