Opened 11 years ago

Last modified 8 years ago

#10312 new defect

very slow matrix construction or block_matrix

Reported by: monniaux Owned by: jason, was
Priority: major Milestone:
Component: linear algebra Keywords: matrix constructor
Cc: zimmerma, cpernet Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by zimmerma)

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

Change History (5)

comment:1 Changed 11 years ago by zimmerma

  • Cc zimmerma added

comment:2 Changed 11 years ago by zimmerma

  • Description modified (diff)

comment:3 Changed 11 years ago by zimmerma

  • Cc cpernet added

comment:4 Changed 8 years ago by mhansen

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

comment:5 Changed 8 years ago by zimmerma

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

Note: See TracTickets for help on using tickets.