#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: |
------------------------------+---------------------------------------------
Description changed by zimmerma:
Old description:
> 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).
New description:
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#comment:2>
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.
