#10312: very slow matrix construction or block_matrix
------------------------------+---------------------------------------------
Reporter: monniaux | Owner: jason, was
Type: defect | Status: new
Priority: major | Milestone:
Component: linear algebra | Keywords: matrix constructor
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------------+---------------------------------------------
The matrix constructor taking a list of rows as input is way too slow
(apparently quadratic in the number of rows) compared to simply
constructing a zero matrix then assigning the lines (quasi linear).
lines=[vector(QQ,[QQ.random_element() for j in xrange(500)]) for i in
xrange(1000)]
import resource
import sys
for length in xrange(0,len(lines)+1,50):
print length,
sys.stdout.flush()
start=resource.getrusage(resource.RUSAGE_SELF).ru_utime
m1 = matrix(QQ, lines[0:length])
end=resource.getrusage(resource.RUSAGE_SELF).ru_utime
time1 = end-start
print time1,
sys.stdout.flush()
start=resource.getrusage(resource.RUSAGE_SELF).ru_utime
m2 = matrix(QQ, length, len(lines[0]))
for i in xrange(length):
m2[i,:] = lines[i]
end=resource.getrusage(resource.RUSAGE_SELF).ru_utime
time2 = end-start
print time2
sys.stdout.flush()
Timings:
50 0.128008 0.028002
100 0.104007 0.056003
150 0.32402 0.088006
200 0.544034 0.112007
250 0.840052 0.140009
300 1.268079 0.180012
350 1.744109 0.204012
400 2.260142 0.228014
450 2.868179 0.264017
500 3.68023 0.292018
550 4.392275 0.32002
600 5.264329 0.340021
650 6.664417 0.384024
700 7.392462 0.408025
750 8.380524 0.448028
800 9.640603 0.47203
850 10.968685 0.500031
900 12.292769 0.532033
950 13.752859 0.560035
1000 15.972999 0.620038
Same problem with sparse matrices:
50 1.584099 1.188075
100 3.116194 2.264142
150 4.748297 3.404213
200 6.904432 4.580286
250 8.928558 5.756359
300 11.564722 6.976436
Same problem with block_matrix (block_matrix is slower than assigning the
blocks directly).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10312>
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.
