Opened 10 years ago

Closed 10 years ago

# Speedup of matrix multiplication

Reported by: Owned by: SimonKing jason, was major sage-4.7 linear algebra matrix multiplication sage-4.7.alpha2 Simon King Rob Beezer N/A

### Description

When multiplying two matrices M and N, typically one first creates a zero matrix of an appropriate matrix space. That means:

• Call `M.matrix_space(...)`.
• This calls `M.parent().matrix_space(...)`.
• This calls `MatrixSpace(...)`.
• This tests, whether the base ring really is a ring and whether the matrix space is already in the cache.

This can obviously be improved:

• `M.matrix_space(...)` should avoid the overhead of calling `M.parent()` but create the matrix space directly.
• It is already known that the base ring is a ring. So, there is no need to test it.
• One may access the cache directly, thus, avoid the overhead of calling `MatrixSpace`.

I guess the ticket belongs to linear algebra. Correct me if I'm wrong.

### comment:1 Changed 10 years ago by SimonKing

• Authors set to Simon King
• Status changed from new to needs_review

I did not run the doc test yet, but I think it already ready for review.

Here are timings. Note that the reduced overhead is most visible when the multiplication itself is trivial.

Without the patch:

```sage: def test(M):
....:     for i in xrange(10^6):
....:         M*=M
....:     return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 51.36 s, sys: 0.16 s, total: 51.52 s
Wall time: 51.67 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 39.16 s, sys: 0.20 s, total: 39.36 s
Wall time: 39.47 s
[1]
sage: m = matrix(ZZ,[[1]])
# apparently there is no overhead for matrices over ZZ
sage: %time test(m)
CPU times: user 7.81 s, sys: 0.15 s, total: 7.96 s
Wall time: 7.99 s
[1]
```

With the patch

```sage: def test(M):
....:     for i in xrange(10^6):
....:         M*=M
....:     return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 33.65 s, sys: 0.30 s, total: 33.95 s
Wall time: 34.05 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 25.41 s, sys: 0.10 s, total: 25.51 s
Wall time: 25.58 s
[1]
sage: m = matrix(ZZ,[[1]])
sage: %time test(m)
CPU times: user 7.62 s, sys: 0.16 s, total: 7.78 s
Wall time: 7.80 s
[1]
```

Thus, over `GF(3)` and `GF(2)` the overhead is clearly reduced.

I don't know how the patch could be doc-tested, as it only concerns the performance.

### comment:2 Changed 10 years ago by SimonKing

• Status changed from needs_review to needs_work

Apparently the small change led to some problems. So, it needs work.

### comment:3 Changed 10 years ago by SimonKing

• Status changed from needs_work to needs_review

The problem was that the matrix spaces are cached with weak references. It could happen that the key was still available, but `_cache[key]` was a reference to `None`. So, in the updated patch I am not simply trying to return `_cache[key]()` but I first test if it is not None.

Back to "needs review"...

### comment:4 Changed 10 years ago by SimonKing

PS:

The timings with the new patch are

```sage: def test(M):
....:     for i in xrange(10^6):
....:         M*=M
....:     return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 37.70 s, sys: 0.18 s, total: 37.89 s
Wall time: 38.00 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 27.09 s, sys: 0.17 s, total: 27.26 s
Wall time: 27.34 s
[1]
```

That's still a lot faster than without patch.

### comment:5 Changed 10 years ago by SimonKing

I updated the patch, so that it cleanly applies to `sage-4.6.2.alpha4`.

### comment:6 follow-up: ↓ 7 Changed 10 years ago by rbeezer

I ran tests in sage/matrix and got failures in matrix_mod2_dense.pyx and matrix2.pyx. Mostly complaints about improper dimensions it seems. The mod2 code appears to have some internal checks that are triggered even before the test itself fails.

### comment:7 in reply to: ↑ 6 Changed 10 years ago by SimonKing

• Status changed from needs_review to needs_work

I ran tests in sage/matrix and got failures in matrix_mod2_dense.pyx and matrix2.pyx. Mostly complaints about improper dimensions it seems. The mod2 code appears to have some internal checks that are triggered even before the test itself fails.

Thank you! As I wrote when I posted my patch, I hadn't run the tests, and then I was working on different tickets. Now I'll try to hunt it down.

### comment:8 Changed 10 years ago by SimonKing

• Status changed from needs_work to needs_review

The test failures were caused by a very stupid mistake: `self.new_matrix()` by default assumes that the dimension of the new matrix is the same as the dimension of the old matrix. In the multiplication algorithms, I saw `self.new_matrix(nrows=self.nrows(),...)`, was not reading further, and thought that we are in the default case, thus, deleted the arguments.

Of course, it continues "(..., ncols=right.ncols())`.

What I did now was to avoid calling `self.nrows()` and `right.ncols()` - direct access to the attributes `self._nrows` and `right._ncols` is faster.

To my surprise, the timings improved a little more:

```sage: def test(M):
....:     for i in xrange(10^6):
....:         M*=M
....:     return M
....:
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 36.67 s, sys: 0.16 s, total: 36.83 s
Wall time: 36.95 s
[1]
sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 26.29 s, sys: 0.14 s, total: 26.43 s
Wall time: 26.50 s
[1]
```

Is it faster to provide arguments with a default value explicitly?

The tests for `sage/matrix/` passed. I am now running all doctests (not the long ones), but I think I can already revert it to "needs review".

### comment:9 Changed 10 years ago by SimonKing

I was updating the patch again. I am now also taking more care of sparse matrices, and I found yet another spot where overhead by calling methods could be reduced.

Updated timings in sage.4.6.2.alpha4

```sage: def test(M):
....:     for i in xrange(10^6):
....:         M*=M
....:     return M
....:
sage: MS = MatrixSpace(GF(5),5,5,sparse=True)
sage: ms = MS([3, 1, 0, 0, 4, 1, 2, 2, 3, 4, 2, 4, 1, 0, 3, 4, 3, 1, 2, 4, 0, 0, 0, 1, 3])
sage: MD = MatrixSpace(GF(5),5,5,sparse=False)
sage: md = MD([3, 1, 0, 0, 4, 1, 2, 2, 3, 4, 2, 4, 1, 0, 3, 4, 3, 1, 2, 4, 0, 0, 0, 1, 3])
```

Without patch:

```sage: %time test(ms)
CPU times: user 42.41 s, sys: 0.01 s, total: 42.43 s
Wall time: 42.57 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
sage: %time test(md)
CPU times: user 53.54 s, sys: 0.20 s, total: 53.74 s
Wall time: 53.90 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
```

With patch:

```sage: %time test(ms)
CPU times: user 29.72 s, sys: 0.03 s, total: 29.75 s
Wall time: 29.84 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
sage: %time test(md)
CPU times: user 34.13 s, sys: 0.36 s, total: 34.49 s
Wall time: 34.59 s
[1 2 4 4 3]
[3 1 2 1 3]
[1 2 2 3 1]
[2 4 0 4 4]
[2 4 2 1 3]
```

Or, with the (dense) examples that I used in the previous posts:

```sage: m = matrix(GF(2),[[1]])
sage: %time test(m)
CPU times: user 22.87 s, sys: 0.12 s, total: 22.99 s
Wall time: 23.06 s
[1]
sage: m = matrix(GF(3),[[1]])
sage: %time test(m)
CPU times: user 33.31 s, sys: 0.12 s, total: 33.43 s
Wall time: 33.52 s
[1]
```

So, the progress is clear.

I am now running doc tests (there was no problem for the previous patch), but I think it is safe to keep it "needs review".

### comment:10 Changed 10 years ago by SimonKing

PS: Long tests in devel/sage/sage and devel/sage/doc pass without error. The error that the patchbot reports is the usual error in startup.py and seems independent of my patch.

### comment:11 Changed 10 years ago by rbeezer

• Status changed from needs_review to needs_info

Simon,

Looks real good. One suggestion - and it really is just a suggestion. Your call.

Two instances of basically:

```try:
from sage.matrix.matrix_space import _cache
MS = _cache[base_ring, nrows, ncols, sparse]()
except KeyError:
return MatrixSpace(base_ring, nrows, ncols, sparse)
if MS is not None:
return MS
return MatrixSpace(base_ring, nrows, ncols, sparse)
```

and a suggested replacement:

```try:
from sage.matrix.matrix_space import _cache
MS = _cache[base_ring, nrows, ncols, sparse]()
except KeyError:
MS = None
if MS is None:
return MatrixSpace(base_ring, nrows, ncols, sparse)
else:
return MS
```

Suggestion uses try/except to form "best guess" for `MS`. Either we find it, or we get `None`. Then if/else returns it, or creates it and returns it.

An extra line, an extra comparison in one case, but the `not` is gone and most importantly, just one place to describe the actual `MatrixSpace` call (instead of two that are identical). Anyway, a toss-up, I'd guess, so just a suggestion.

In the meantime, I am going to run the full test suite right now.

Rob

### comment:12 follow-up: ↓ 13 Changed 10 years ago by rbeezer

Passed all long tests. So, other than my suggestion above, this looks ready to go.

### comment:13 in reply to: ↑ 12 ; follow-up: ↓ 14 Changed 10 years ago by SimonKing

• Status changed from needs_info to needs_review

Passed all long tests. So, other than my suggestion above, this looks ready to go.

Can you turn your suggestion into a referee patch? I wouldn't object to the change.

Cheers,

Simon

### comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 10 years ago by rbeezer

Can you turn your suggestion into a referee patch? I wouldn't object to the change.

Done and attached. Passes all long tests with the change. When you are satisfied with my changes, go ahead and flip this to "positive review" - everything looks good on my end.

Thanks for the speed increase!

Rob

### comment:15 in reply to: ↑ 14 Changed 10 years ago by SimonKing

• Reviewers set to Rob Beezer
• Status changed from needs_review to positive_review

Hi Rob,

Can you turn your suggestion into a referee patch? I wouldn't object to the change.

Done and attached. Passes all long tests with the change. When you are satisfied with my changes, go ahead and flip this to "positive review"

Thanks for the speed increase!

You're welcome! After all, the speed increase was in my own interest.

Cheers,

Simon

### comment:16 Changed 10 years ago by jdemeyer

• Milestone changed from sage-4.6.2 to sage-4.7

### comment:17 follow-up: ↓ 18 Changed 10 years ago by jdemeyer

• Status changed from positive_review to needs_work

The commit message of the patch should be broken up in multiple lines instead of one long line. The first line should stand by itself and must mention the ticket number, a more detailed message can come on following lines. Use `hg qrefresh -e` to change the commit message.

### Changed 10 years ago by SimonKing

Improve performance of matrix multiplication by using a shortpath to matrix spaces and a shortpath in multiplication algorithms for creating a zero matrix

### comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 10 years ago by SimonKing

• Status changed from needs_work to positive_review

The commit message of the patch should be broken up in multiple lines instead of one long line. The first line should stand by itself and must mention the ticket number, a more detailed message can come on following lines. Use `hg qrefresh -e` to change the commit message.

Both patches did mention the ticket number, and I think it is questionable whether the message of my original patch was to long. Anyway, I just replaced it, and I hope you'll find that it is fine.