very slow matrix construction or block_matrix

[bd4edba6-a6b9-4042-be56-832c680989e3]

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).

CC: @zimmermann6 @ClementPernet

Component: linear algebra

Keywords: matrix constructor

Issue created by migration from https://trac.sagemath.org/ticket/10312

[zimmermann6]

Description changed:

--- 
+++ 
@@ -1,5 +1,6 @@
 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
@@ -24,8 +25,10 @@
   time2 = end-start
   print time2
   sys.stdout.flush()
+```
+Timings:

-Timings:
+```
 50 0.128008 0.028002
 100 0.104007 0.056003
 150 0.32402 0.088006
@@ -46,13 +49,15 @@
 900 12.292769 0.532033
 950 13.752859 0.560035
 1000 15.972999 0.620038
+```
+Same problem with sparse matrices:

-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).

[mwhansen]

comment:4

I think that this is only a problem with sparse matrices now.

[zimmermann6]

comment:5

indeed with Sage 5.9 I get on a AMD Phenom(tm) II X2 B55 with the code in the description:

50 0.028002 0.012001
100 0.120007 0.036002
150 0.15601 0.052003
200 0.188012 0.076005
250 0.220014 0.092005
300 0.31202 0.116007
350 0.360023 0.128008
400 0.400025 0.15601
450 0.424026 0.16001
500 0.532033 0.200013
550 0.584036 0.200013
600 0.608038 0.236015
650 0.620038 0.240015
700 0.752047 0.276018
750 0.820051 0.260016
800 0.752047 0.31202
850 0.988061 0.30802
900 0.928058 0.348021
950 0.964061 0.336021
1000 1.092068 0.388024

It is still slower than assigning the lines one per one, but quasi linear now.

David, please could you provide code for the sparse and block matrices?

Paul