Opened 10 years ago
Closed 10 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 10 years ago by
comment:2 Changed 10 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 10 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 10 years ago by
Changed 10 years ago by
comment:4 Changed 10 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 10 years ago by
By the way, I fail with uploading files. Only apply: 10568-speedup-QQmatrix-lmul
Changed 10 years ago by
comment:6 Changed 10 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 10 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 10 years ago by
- Cc rbeezer added
comment:9 Changed 10 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 10 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 10 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 10 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 10 years ago by
- Status changed from needs_work to positive_review
comment:14 in reply to: ↑ 12 Changed 10 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 10 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 10 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