#1191: wrap pari's matsolvemodn for A.solve_right over Z/nZ
--------------------------------------------------+-------------------------
Reporter: malb | Owner: was
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.9
Component: linear algebra | Resolution:
Keywords: solve_right, matsolvemod, Zmod | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Robert Harron | Merged in:
Dependencies: #14391 | Stopgaps:
--------------------------------------------------+-------------------------
Comment (by robharron):
Here are some times (I temporarily added a method .solve_left_slow that
uses the f.g. over a pid code; the latter naturally does things on the
left):
{{{
sage: N = 124; r = 21; c = 17; M = MatrixSpace(Zmod(N), r, c); A =
M.random_element(); AL = A.lift(); X = Zmod(N) ** c; x =
X.random_element(); xL = x.lift(); bL = AL * xL; bL = bL % N; AT =
A.transpose(); b = (Zmod(N) ** r)(bL)
sage: timeit('A.solve_right(b)')
125 loops, best of 3: 3.72 ms per loop
sage: timeit('AT.solve_left_slow(b)')
5 loops, best of 3: 707 ms per loop
sage: N = 12; r = 50; c = 38; M = MatrixSpace(Zmod(N), r, c); A =
M.random_element(); AL = A.lift(); X = Zmod(N) ** c; x =
X.random_element(); xL = x.lift(); bL = AL * xL; bL = bL % N; AT =
A.transpose(); b = (Zmod(N) ** r)(bL)
sage: timeit('A.solve_right(b)')
5 loops, best of 3: 44.3 ms per loop
sage: timeit('AT.solve_left_slow(b)')
5 loops, best of 3: 6.41 s per loop
sage: N = 4829; r = 9; c = 5; M = MatrixSpace(Zmod(N), r, c); A =
M.random_element(); AL = A.lift(); X = Zmod(N) ** c; x =
X.random_element(); xL = x.lift(); bL = AL * xL; bL = bL % N; AT =
A.transpose(); b = (Zmod(N) ** r)(bL)
sage: timeit('A.solve_right(b)')
625 loops, best of 3: 343 µs per loop
sage: timeit('AT.solve_left_slow(b)')
5 loops, best of 3: 133 ms per loop
sage: N = 2634095876; r = 21; c = 17; M = MatrixSpace(Zmod(N), r, c); A =
M.random_element(); AL = A.lift(); X = Zmod(N) ** c; x =
X.random_element(); xL = x.lift(); bL = AL * xL; bL = bL % N; AT =
A.transpose(); b = (Zmod(N) ** r)(bL)
sage: timeit('A.solve_right(b)')25 loops, best of 3: 13 ms per loop
sage: timeit('AT.solve_left_slow(b)')5 loops, best of 3: 799 ms per loop
sage: sage: N = 23457602398746509872634095876; r = 21; c = 17; M =
MatrixSpace(Zmod(N), r, c); A = M.random_element(); AL = A.lift(); X =
Zmod(N) ** c; x = X.random_element(); xL = x.lift(); bL = AL * xL; bL = bL
% N; AT = A.transpose(); b = (Zmod(N) ** r)(bL)
sage: timeit('A.solve_right(b)')
5 loops, best of 3: 66.5 ms per loop
sage: timeit('AT.solve_left_slow(b)')
5 loops, best of 3: 1.18 s per loop
sage: N = 29834756092364523457602398746509872634095876; r = 21; c = 17; M
= MatrixSpace(Zmod(N), r, c); A = M.random_element(); AL = A.lift(); X =
Zmod(N) ** c; x = X.random_element(); xL = x.lift(); bL = AL * xL; bL = bL
% N; AT = A.transpose(); b = (Zmod(N) ** r)(bL)
sage: timeit('A.solve_right(b)')
5 loops, best of 3: 231 ms per loop
sage: timeit('AT.solve_left_slow(b)')
5 loops, best of 3: 1.54 s per loop
}}}
I also attached a code snippet of .solve_left_slow to this ticket for
transparency and posterity!
Replying to [comment:5 malb]:
> Can you post some timings comparing the two approaches (I am curious
about larger dimensions & bitsizes)? The patch itself looks fine to me.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/1191#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.
