id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
16116 Multiplication of dense cyclotomic matrices should be faster jipilab "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:
- libgap wrappers
- generic matrix (`matrix_generic_dense.Matrix_generic_dense`)
- the specialized inadapted class that is used by default now in Sage (`matrix_cyclo_dense.Matrix_cyclo_dense`)
Concrete tickets:
- #23704: getitem/setitem for libgap elements
- #23706: gap class for matrices + be able to change the implementation
-----------------------------------------
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:
{{{
sage: def make_matrix1(R,a,b):
....: return matrix(R, 3, [[-1, 1, 2*a],
....: [-4*a*b - 1, 4*a*b + 4*b^2, 4*a*b + 2*a],
....: [-2*a, 2*a + 2*b, 2*a]])
sage: PR. = PolynomialRing(QQ)
sage: I = Ideal(x^2 - 1/2*x - 1/4, y^3 - 1/2*y^2 - 1/2*y + 1/8)
sage: Q = PR.quotient(I)
sage: elmt = make_matrix1(Q, x, y)
sage: %timeit elmt^2
1000 loops, best of 3: 1.17 ms per loop
sage: UCF. = UniversalCyclotomicField()
sage: ae = (E(10)+~E(10))/2 #same value as a
sage: be = (E(14)+~E(14))/2 #same value as b
sage: m = make_matrix1(UCF, ae, be)
sage: %timeit m^2
100 loops, best of 3: 8.13 ms per loop
sage: CF. = CyclotomicField(2*5*7)
sage: af = (F^7+~F^7)/2 #same value as a
sage: bf = (F^5+~F^5)/2 #same value as b
sage: m2 = make_matrix1(CF, af, bf)
sage: %timeit m2^2
100 loops, best of 3: 4.99 ms per loop
}}}
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.
{{{
sage: def make_matrix2(R, a):
....: return matrix(R, 3, [[-2*a, 1, 6*a+2],
....: [-2*a, 2*a, 4*a+1],
....: [0, 0, 1]])
sage: PR. = PolynomialRing(QQ)
sage: I = Ideal(x^2 - 1/2*x - 1/4)
sage: Q = PR.quotient(I)
sage: elmt_uni = make_matrix2(Q, x)
sage: %timeit elmt_uni*elmt_uni
1000 loops, best of 3: 1.46 ms per loop
sage: CF. = CyclotomicField(2*5)
sage: f5 = (F+~F)/2
sage: m = make_matrix2(CF, f5)
sage: type(m)
sage: m.parent()
Full MatrixSpace of 3 by 3 dense matrices over
Cyclotomic Field of order 10 and degree 4
sage: %timeit m*m
100 loops, best of 3: 1.98 ms per loop
}}}
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.
{{{
sage: CF. = CyclotomicField(2*5)
sage: f5 = (F+~F)/2
sage: m = make_matrix2(CF, f5)
sage: m.parent()
Full MatrixSpace of 3 by 3 dense matrices over
Cyclotomic Field of order 10 and degree 4
sage: type(m)
sage: %timeit m*m
1000 loops, best of 3: 251 µs per loop
}}}
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?" task new major sage-8.1 linear algebra cyclotomic field, matrix, multiplication, benchmark, days57, days88 sage-combinat nthiery stumpc5 vdelecroix was N/A