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:

Status badges

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.

Attachments (2)

trac_10763-speedup-matrix-multiplication-reviewer.patch (1.5 KB) - added by rbeezer 10 years ago.
trac10763-speedup_matrix_multiplication.patch (4.5 KB) - added by SimonKing 10 years ago.
Improve performance of matrix multiplication by using a shortpath to matrix spaces and a shortpath in multiplication algorithms for creating a zero matrix

Download all attachments as: .zip

Change History (22)

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: 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

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 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: 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: Changed 10 years ago by SimonKing

  • 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

comment:14 in reply to: ↑ 13 ; follow-up: Changed 10 years ago by 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" - 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,

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 jdemeyer

  • Milestone changed from sage-4.6.2 to sage-4.7

comment:17 follow-up: 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: Changed 10 years ago by SimonKing

  • 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 jdemeyer

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 jdemeyer

  • Merged in set to sage-4.7.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.