Opened 10 years ago
Closed 10 years ago
#10763 closed enhancement (fixed)
Speedup of matrix multiplication
Reported by: | SimonKing | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | linear algebra | Keywords: | matrix multiplication |
Cc: | Merged in: | sage-4.7.alpha2 | |
Authors: | Simon King | Reviewers: | Rob Beezer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
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 callingM.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.
Attachments (2)
Change History (22)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- 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
- 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
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
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
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
- Status changed from needs_review to needs_work
Replying to 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.
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
- 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
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
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
- 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
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
- Status changed from needs_info to needs_review
Replying to rbeezer:
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
Changed 10 years ago by
comment:14 in reply to: ↑ 13 ; follow-up: ↓ 15 Changed 10 years ago by
Replying to SimonKing:
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
- Reviewers set to Rob Beezer
- Status changed from needs_review to positive_review
Hi Rob,
Replying to rbeezer:
Replying to SimonKing:
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"
Done, adding your name in the "Reviewer" field.
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
- Milestone changed from sage-4.6.2 to sage-4.7
comment:17 follow-up: ↓ 18 Changed 10 years ago by
- 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
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
- Status changed from needs_work to positive_review
Replying to jdemeyer:
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.
comment:19 in reply to: ↑ 18 Changed 10 years ago by
Replying to SimonKing:
I think it is questionable whether the message of my original patch was to long.
Just to clarify: the message itself was not too long, the problem was that the whole message was one long line without newlines. It should be wrapped to multiple lines instead (as you did in this case).
comment:20 Changed 10 years ago by
- Merged in set to sage-4.7.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
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:
With the patch
Thus, over
GF(3)
andGF(2)
the overhead is clearly reduced.I don't know how the patch could be doc-tested, as it only concerns the performance.