Opened 11 years ago

Closed 10 years ago

# Multiplying sparse matrices by integers is unnecessarily slow

Reported by: Owned by: mderickx jason, was major sage-4.7 linear algebra sage-4.7.alpha1 Maarten Derickx Rob Beezer N/A

### 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
```

### comment:1 Changed 11 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 11 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 11 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
```

### comment:4 Changed 11 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:6 Changed 10 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 10 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:9 Changed 10 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 10 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 10 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: ↓ 14 Changed 10 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 10 years ago by mderickx

• Status changed from needs_work to positive_review

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

• Status changed from positive_review to needs_work

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 10 years ago by mderickx

Use this one, the others are old version

### comment:15 Changed 10 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 10 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.