#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):
'''bsd.math'''
{{{
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 2.87 s, sys: 0.01 s, total: 2.88 s
Wall time: 2.88 s
sage: %time _ = A._multiply_strassen(B, 50)
CPU times: user 1.47 s, sys: 0.01 s, total: 1.47 s
Wall time: 1.47 s
sage: %time _ = A._multiply_strassen(B,100)
CPU times: user 1.24 s, sys: 0.01 s, total: 1.24 s
Wall time: 1.24 s
sage: %time _ = A._multiply_strassen(B,150)
CPU times: user 1.16 s, sys: 0.01 s, total: 1.17 s
Wall time: 1.17 s
sage: %time _ = A._multiply_strassen(B,200)
CPU times: user 1.16 s, sys: 0.01 s, total: 1.17 s
Wall time: 1.17 s
}}}
{{{
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 3.72 s, sys: 0.00 s, total: 3.72 s
Wall time: 3.72 s
1000 x 1000 dense matrix over Finite Field of size 2147483647
sage: %time _ = A._multiply_strassen(B, 50)
CPU times: user 2.55 s, sys: 0.01 s, total: 2.55 s
Wall time: 2.55 s
sage: %time _ = A._multiply_strassen(B,100)
CPU times: user 2.53 s, sys: 0.01 s, total: 2.54 s
Wall time: 2.54 s
sage: %time _ = A._multiply_strassen(B,150)
CPU times: user 2.68 s, sys: 0.00 s, total: 2.69 s
Wall time: 2.69 s
sage: %time _ = A._multiply_strassen(B,200)
CPU times: user 2.68 s, sys: 0.00 s, total: 2.69 s
Wall time: 2.69 s
}}}
So 100 is much better than 20, but not necessarily optimal.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4968#comment:30>
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.
