#4968: implement fast linear algebra modulo n < 2^31
----------------------------------+-----------------------------------------
Reporter: malb | Owner: was
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-wishlist
Component: linear algebra | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #10281 | Stopgaps:
----------------------------------+-----------------------------------------
Comment (by malb):
'''Cicero''' is less conclusive as it's too loaded for benchmarketing.
Anyway, here are the numbers:
'''2^24^'''
{{{
sage: A = random_matrix(GF(previous_prime(2^24)),1000,1000)
sage: B = random_matrix(GF(previous_prime(2^24)),1000,1000)
sage: %time _ = A._multiply_strassen(B, 20)
CPU times: user 25.93 s, sys: 0.03 s, total: 25.95 s
Wall time: 85.44 s
sage: %time _ = A._multiply_strassen(B, 50)
CPU times: user 21.48 s, sys: 0.04 s, total: 21.52 s
Wall time: 68.51 s
sage: %time _ = A._multiply_strassen(B,100)
CPU times: user 21.99 s, sys: 0.11 s, total: 22.09 s
Wall time: 70.36 s
sage: %time _ = A._multiply_strassen(B,150)
CPU times: user 23.95 s, sys: 0.05 s, total: 24.01 s
Wall time: 76.56 s
}}}
'''2^31'''
{{{
sage: A = random_matrix(GF(previous_prime(2^31)),1000,1000)
sage: B = random_matrix(GF(previous_prime(2^31)),1000,1000)
sage: %time _ = A._multiply_strassen(B, 20)
CPU times: user 25.93 s, sys: 0.08 s, total: 26.00 s
Wall time: 83.17 s
sage: %time _ = A._multiply_strassen(B, 50)
CPU times: user 21.47 s, sys: 0.06 s, total: 21.53 s
Wall time: 68.69 s
sage: %time _ = A._multiply_strassen(B,100)
CPU times: user 22.02 s, sys: 0.06 s, total: 22.08 s
Wall time: 70.31 s
sage: %time _ = A._multiply_strassen(B,150)
CPU times: user 23.92 s, sys: 0.14 s, total: 24.06 s
Wall time: 76.67 s
}}}
''What I take away from these numbers:'' increasing the default cutoff
from 20 to 100 makes Sage twice as fast on some mainstream architectures
(64-bit Linux, Xeon), about 1.7x faster on others (64-bit OSX) and
probably slightly faster on less mainstream architectures (32-bit Linux on
Pentium4). Am I missing something here?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4968#comment:31>
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.
