Opened 9 years ago

Closed 9 years ago

#10568 closed enhancement (fixed)

Multiplying sparse matrices by integers is unnecessarily slow

Reported by: mderickx Owned by: jason, was
Priority: major Milestone: sage-4.7
Component: linear algebra Keywords:
Cc: Merged in: sage-4.7.alpha1
Authors: Maarten Derickx Reviewers: Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

The below shows that a speedup of a factor 20 or more can be obtained in certain cases

sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720)
sage: time a=2*m
CPU times: user 8.17 s, sys: 0.02 s, total: 8.19 s
Wall time: 8.33 s
sage: time b=diagonal_matrix(QQ,1240,2,sparse=True)*m
CPU times: user 0.33 s, sys: 0.00 s, total: 0.33 s
Wall time: 0.34 s
sage: a==b
True

Attachments (4)

10553-DiamondBrackedSpeedup (2.1 KB) - added by mderickx 9 years ago.
10568-speedup-QQmatrix-lmul.2 (1.4 KB) - added by mderickx 9 years ago.
10568-speedup-QQmatrix-lmul (2.3 KB) - added by mderickx 9 years ago.
10568-speedup-QQmatrix-lmul.patch (2.8 KB) - added by mderickx 9 years ago.
Use this one, the others are old version

Download all attachments as: .zip

Change History (20)

comment:1 Changed 9 years ago by mderickx

it can be even faster then the second suggestion. with still the same m as above:

sage: time for key in m._dict(): m._dict()[key]=2*(m._dict()[key]) CPU times: user 0.03 s, sys: 0.00 s, total: 0.04 s Wall time: 0.04 s

comment:2 Changed 9 years ago by mderickx

With the patch applied I now get:

sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720)
sage: set_verbose(2)
sage: m._lmul_(2)
verbose 2 (_lmul_) scalar multiplying
verbose 2 (_lmul_) scalar multiplying finished (time = 0.033165)
1240 x 3720 sparse matrix over Rational Field (type 'print m.str()' to see all of the entries)
sage: time 2*m
CPU times: user 15.97 s, sys: 0.04 s, total: 16.01 s
Wall time: 16.36 s
1240 x 3720 sparse matrix over Rational Field
sage: time m*2
CPU times: user 15.93 s, sys: 0.04 s, total: 15.97 s
Wall time: 16.46 s
1240 x 3720 sparse matrix over Rational Field

So the newer and faster _lmul_ is there but for some reason it is not called.

comment:3 Changed 9 years ago by mderickx

And its not because 2 is an integer and not a rational since the following also doesn't work:

sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720) 
sage: set_verbose(2)
sage: QQ(2)*m

Changed 9 years ago by mderickx

Changed 9 years ago by mderickx

comment:4 Changed 9 years ago by mderickx

  • Status changed from new to needs_review

Ok the problem was that I had to cpdef the _lmul_ operator. It's now dramatically faster as the following shows:

sage: M=MatrixSpace(QQ,1240,3720,sparse=true)
sage: m=M.random_element(density=4/3720) 
sage: set_verbose(2)
sage: time QQ(2)*m
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
1240 x 3720 sparse matrix over Rational Field

The old code was multiplying sparse matrices as if they were still regular (dense) matrices, so no wonder it was terribly slow.

comment:5 Changed 9 years ago by mderickx

By the way, I fail with uploading files. Only apply: 10568-speedup-QQmatrix-lmul

Changed 9 years ago by mderickx

comment:6 Changed 9 years ago by rbeezer

  • Authors set to Maarten Derickx
  • Status changed from needs_review to needs_info

Maarten,

Looks real good and is a good thing to get into Sage. Seems like sparse matrices are often neglected. I bet there is more like this to be done in other places. I used just 10568-speedup-QQmatrix-lmul, which I hope was the right file. Some comments and suggestions follow.

Rob

  • I like the HUGE doctest. ;-)
  • A doctest like the following might be a nice addition - it'd show a multiplier outside the base ring cooperating with the coercion model and doing the right thing.
sage: F = FiniteField(3)
sage: two = F(2)
sage: A = matrix(ZZ, 3, range(30), sparse=True)
sage: B = two*A; B
[0 2 1 0 2 1 0 2 1 0]
[2 1 0 2 1 0 2 1 0 2]
[1 0 2 1 0 2 1 0 2 1]
sage: B.parent()
Full MatrixSpace of 3 by 10 sparse matrices over Finite Field of size 3
  • How about an INPUT: and OUTPUT: block in the docstring? Even though these internal methods don't show in tab-completion, you can still view them in the notebook with formatting, so I think the consistent style is a good idea.
  • If you name your files as *.patch then Trac gives a very nice red-green/leaving-entering view and my local patch viewer (kompare) will do tab-completion on the filename. ;-)
  • I'd imagine the release manager can clear out the two uploads you didn't want?

comment:7 Changed 9 years ago by mderickx

  • Status changed from needs_info to needs_review

Yeah, I thought the HUGE doctest was nice to :). It at least shows what is different about this function compared to the function it overwrites. And it makes sure that if someone accidentally replaces this function by something not sparse that the doctest would never complete :).

I don't think the doctest you suggest is a good addition in this particular place, from the reference manual http://www.sagemath.org/doc/reference/coercion.html:

If R is the base of S (as in the first example), simply implement
_rmul_ and/or _lmul_ on the Elements of S. In this case r * s gets
handled as s._rmul_(r) and s * r as s._lmul_(r). The argument to
_rmul_ and _lmul_ are guaranteed to be Elements of the base of S (with
coercion happening beforehand if necessary).

So the new code has noting to do with coercion. I really think that tests should be performed in the place where the relevant code is. Since there is no coercion happening in this low level _lmul_ function this should not be tested here.

Input and output block are added and now with .patch extension :

comment:8 Changed 9 years ago by mderickx

  • Cc rbeezer added

comment:9 Changed 9 years ago by rbeezer

  • Cc rbeezer removed
  • Milestone set to sage-4.6.2
  • Reviewers set to Rob Beezer
  • Status changed from needs_review to positive_review

Maarten,

I like my doctests to mash up as much of Sage as possible, and show how different things work together. But you have a good argument. And as an underscore method it's not that critical, anyway.

Trac Tip: once somebody comments on a ticket, they get email for life on that one, so no need to add such a person to the cc.

Passes all tests. Nice contribution!

Rob

comment:10 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-4.6.2 to sage-4.7
  • Summary changed from multipying sparse matrices by integers in unnecceraly slow to Multiplying sparse matrices by integers is unnecessarily slow

comment:11 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

The patch seems not to be a proper HG changeset. Patches should be made using hg export tip (and not hg diff).

comment:12 follow-up: Changed 9 years ago by mderickx

Sorry, jeroen. I thought uploading files from my .hg/patches/ was easier then having to create a patch again each time. But apparently the files are not stored there in a proper patch format. I uploaded a proper one now.

comment:13 Changed 9 years ago by mderickx

  • Status changed from needs_work to positive_review

comment:14 in reply to: ↑ 12 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Replying to mderickx:

Sorry, jeroen. I thought uploading files from my .hg/patches/ was easier then having to create a patch again each time. But apparently the files are not stored there in a proper patch format. I uploaded a proper one now.

I think you did something wrong, because the "new" file is exactly the same as the old.

Changed 9 years ago by mderickx

Use this one, the others are old version

comment:15 Changed 9 years ago by mderickx

  • Status changed from needs_work to positive_review

I must be the worst person ever with uploading patches. So here is the right one finally I hope.

comment:16 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.