#10628: initialization of matrices from vectors or list of lists can be way
faster
------------------------------+---------------------------------------------
Reporter: mderickx | Owner: jason, was
Type: enhancement | Status: needs_review
Priority: major | Milestone:
Component: linear algebra | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Maarten Derickx, Simon King
Merged: | Dependencies:
------------------------------+---------------------------------------------
Changes (by newvalueoldvalue):
* priority: minor => major
* status: needs_work => needs_review
* author: => Maarten Derickx, Simon King
Comment:
I have attached a patch with my suggested code (with some minor
modifications) and a new doc test.
Also I can provide more timings. They show that the second patch not only
provides more flexibility but also a mild speedup on top of what is
achieved by the first patch.
Here are the timings on my computer for the examples you gave, with both,
only the first, and no patch, respectively (I considered the wall time in
each case):
{{{
sage: M=MatrixSpace(GF(46337),400)
sage: m=M.random_element()
sage: m1=m.columns()
sage: time M(m1)
400 x 400 dense matrix over Finite Field of size 46337
Time: CPU 0.68 s, Wall: 0.67 s
// without second patch: 0.72 s
// without patches: 1.46 s
sage: M=MatrixSpace(GF(46337),400)
sage: m=M.random_element()
sage: m1=m.columns()
sage: time M(m1)
400 x 400 dense matrix over Finite Field of size 46337
Time: CPU 0.66 s, Wall: 0.66 s
// without second patch: 0.66 s
// without patches: 1.38 s
}}}
The ticket description mentions the creation from list of lists, but there
were no timings, so far.
{{{
sage: MS = MatrixSpace(GF(5),1000)
sage: L = 1000*[[GF(5)(i) for i in range(1000)]]
sage: %time M = MS(L)
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.03 s
// without second patch: 0.04 s
// without both patches: 5.14 s
sage: sum(L,[]) == M.list()
True
}}}
If a matrix is created from a plain list (not list of lists), the first
patch had a slow down. The second patch brings it back to the original
speed:
{{{
sage: MS = MatrixSpace(GF(5),4000)
# Matrix creation by a single list
sage: L = 4000*[GF(5)(i) for i in range(4000)]
sage: %time M = MS(L)
CPU times: user 0.20 s, sys: 0.02 s, total: 0.22 s
Wall time: 0.23 s
// without second patch: 0.38 s
// without both patches: 0.21 s
}}}
Here are the new doc tests, that would fail without the second patch:
{{{
sage: MS = MatrixSpace(ZZ,4,2)
sage: MS0 = MatrixSpace(ZZ,2)
A list of matrices::
sage: MS.matrix([MS0([1,2,3,4]), MS0([5,6,7,8])])
[1 2]
[3 4]
[5 6]
[7 8]
A mixed list of matrices and vectors::
sage: MS.matrix( [MS0([1,2,3,4])] + list(MS0([5,6,7,8])) )
[1 2]
[3 4]
[5 6]
[7 8]
}}}
Last, allow me to increase the priority of the ticket. An improvement from
more than 5 seconds to less than 0.05 seconds is not "minor".
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10628#comment:10>
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.
