-
-
Notifications
You must be signed in to change notification settings - Fork 453
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Multiplication of dense cyclotomic matrices should be faster #16116
Comments
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
comment:5
Hello, With #18152, I got a 10x speedup old version:
new version:
Vincent |
comment:6
And using libgap directly is even faster
So, as written in the bottom of the description in #18152, we should wrap GAP matrices to deal with dense cyclotomics matrices in Sage. Vincent |
comment:7
Hello, I reformatted your example such that they fit in less lines (it can easily switched back to your original version if you do not like it). I had a quick look at the code for dense cyclotomic matrices. The implementation is quite old and uses a lot of reduction mod p (even for multiplication). The code calls a lot of Python code like creating a finite field, creating a matrix space, etc which are relatively slow compared to a small matrix multiplication. Did you try multiplying larger matrices (i.e. 10x10 or 15x15)? On the other hand, I am pretty sure that some cleaning could be of great speed up. By cleaning I mean:
Vincent |
This comment has been minimized.
This comment has been minimized.
comment:8
Replying to @videlec:
I designed and implemented the algorithm for dense cyclotomic matrices. We were optimizing for larger matrices... which in the context of modular forms means at least 100 rows (and often much, much more). GAP/pari on the other hand optimize for relatively tiny matrices. The asymptotically fast algorithms for large matrices are totally different than for small... |
comment:9
Replying to @williamstein:
All right. I now understand better what I read! I see two possibilities.
Vincent |
comment:10
Hi, In the case I'm interested in, it is definitely for small sizes. Say up to 20-25 at the very very biggest. Most commonly it is going to be between 3 and 10. This is related to the tickets #15703, #16087. How to proceed to add another multiplication to the matrices that could be used for small matrices? Are there examples around with such a thing? I could look at it... |
comment:11
Replying to @jplab:
Matrices over ZZ used to have special code for small versus large. I think now that variation in algorithms is mainly hidden by calling FLINT. Look into it. |
comment:12
Replying to @williamstein:
William, are you sure that the representation you used in In the present case, I would rather modify |
comment:13
No. In fact, I'm pretty sure they are not what you would want for small sizes. |
comment:14
We also have a related issue:
Where the issue is coming from having a scalar times a matrix. Here's some profiling info of doing it over the cyclotomic field:
This is nowhere to be found when doing it over the number field. (For very small matrices this isn't a problem per se, but it still is visible when profiling.) So my conclusion is that we are doing something wrong with how we handle multiplication with cyclotomics in the matrix versus our generic dense cases. |
comment:15
I should note that I get very different profiling when I reverse the orders of the tensor product, which from the naive implementation of the tensor product and thoughts about scalar multiplication surprises me:
There are quite a lot more function calls (~10x) to the
versus
|
comment:16
The part which handles speeding up the tensor product is now #19258. |
comment:17
It seems that matrix multiplication over the universal cyclotomic field is on the same order as the polynomial ring (probably because it uses the generic matrix class):
However for UCF matrices, I'm thinking we might benefit from either using (lib)GAP's matrix multiplication or internally storing the GAP element and only converting it to a Sage UCF element as necessary. See #19821 for a use-case. |
comment:18
At least on sage-7.0.beta2, wrapping GAP matrices for the examples mentioned in the ticket description will not bring any magic
versus
We are below x2 speedup. But in this example the matrix is small and coefficients relatively dense (~25 nonzero coefficients). Though, the gain is significant with 10x10 dense matrices with small coefficients
We might update the ticket description accordingly. Two concrete propositions are:
|
comment:19
A 30-40% speed reduction is nothing to scoff at either. So from that data, I think for dense matrices over the UCF we should always just wrap GAP. |
Changed keywords from cyclotomic field, matrix, multiplication, benchmark, days57 to cyclotomic field, matrix, multiplication, benchmark, days57, days88 |
This ticket organizes various improvements in order to get faster matrices over cyclotomic fields. The aim is to implement and compare three different ways to perform such computation:
matrix_generic_dense.Matrix_generic_dense
)matrix_cyclo_dense.Matrix_cyclo_dense
)Concrete tickets:
Description from several years ago...
The multiplication of matrices with a (universal) cyclotomic fields as base ring could be optimized as the following profiling shows:
The three matrices elmt, m and m2 are the same encoded into 3 different base rings. It would be natural to think that the cyclotomic field be the optimal field to do computations, but it does not seem to be the case in practice.
Here is a univariate example.
Then, I disactivated the verification on cyclotomic fields on line 962 of the file /src/sage/matrix/matrix_space.py to get a matrix_generic_dense instead of matrix_cyclo_dense.
The gain is significant. Is there a known use cases where the specialized implementation is faster than the generic one? If yes, should we make some threshold test to choose between the two implementations?
CC: @sagetrac-sage-combinat @nthiery @stumpc5 @videlec @williamstein
Component: linear algebra
Keywords: cyclotomic field, matrix, multiplication, benchmark, days57, days88
Issue created by migration from https://trac.sagemath.org/ticket/16116
The text was updated successfully, but these errors were encountered: