# Changes between Version 2 and Version 7 of Ticket #16116

Ignore:
Timestamp:
04/11/15 13:15:35 (5 years ago)
Comment:

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:

• declare `cdef` variables wherever possible
• let as minimum as possible `import` inside the methods
• ...

You can also do some profiling on the code (using "%prun" and "%crun"), see #17689 which is not yet in the current development release.

Vincent

Unmodified
Removed
Modified
• ## Ticket #16116

• Property Milestone changed from `sage-6.2` to `sage-6.4`
• ## Ticket #16116 – Description

 v2 {{{ sage: x,y=var('x,y') sage: PR=PolynomialRing(QQ,[x,y]) 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: a,b=Q.gens() sage: elmt=matrix(Q,[[-1, 1, 2*x],[-4*x*y - 1, 4*x*y + 4*y^2, 4*x*y + 2*x],[-2*x, 2*x + 2*y, 2*x]]) sage: %timeit elmt^2 1000 loops, best of 3: 1.17 ms per loop 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=matrix(UCF,[[-1, 1, 2*ae],[-4*ae*be - 1, 4*ae*be + 4*be^2, 4*ae*be + 2*ae],[-2*ae, 2*ae + 2*be, 2*ae]]) sage: %timeit m^2 100 loops, best of 3: 8.13 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=matrix(CF,[[-1, 1, 2*af],[-4*af*bf - 1, 4*af*bf + 4*bf^2, 4*af*bf + 2*af],[-2*af, 2*af + 2*bf, 2*af]]) sage: %timeit m2^2 100 loops, best of 3: 4.99 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 }}} 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: PR=PolynomialRing(QQ,[x]) sage: I=Ideal(x^2 - 1/2*x - 1/4) sage: Q=PR.quotient(I) sage: elmt_uni=matrix(Q,[[-2*x, 1, 6*x + 2],[-2*x, 2*x, 4*x + 1],[0,0,1]]) 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=matrix(CF,[[-2*f5, 1, 6*f5 + 2],[-2*f5, 2*f5, 4*f5 + 1],[0,0,1]]) 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 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 }}} {{{ sage: CF.=CyclotomicField(2*5) sage: f5=(F+~F)/2 sage: m=matrix(CF,[[-2*f5, 1, 6*f5 + 2],[-2*f5, 2*f5, 4*f5 + 1],[0,0,1]]) 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 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 }}}