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)
Change History (20)
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
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
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
Changed 9 years ago by
comment:4 Changed 9 years ago by
- 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
By the way, I fail with uploading files. Only apply: 10568-speedup-QQmatrix-lmul
Changed 9 years ago by
comment:6 Changed 9 years ago by
- 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:
andOUTPUT:
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
- 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
- Cc rbeezer added
comment:9 Changed 9 years ago by
- 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
- 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
- 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: ↓ 14 Changed 9 years ago by
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
- Status changed from needs_work to positive_review
comment:14 in reply to: ↑ 12 Changed 9 years ago by
- 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.
comment:15 Changed 9 years ago by
- 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
- Merged in set to sage-4.7.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
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