Changes between Version 2 and Version 7 of Ticket #16116


Ignore:
Timestamp:
04/11/15 13:15:35 (6 years ago)
Author:
vdelecroix
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

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #16116

    • Property Milestone changed from sage-6.2 to sage-6.4

  • Ticket #16116 – Description

    v2 v7  
    22
    33{{{
    4     sage: x,y=var('x,y')
    5     sage: PR=PolynomialRing(QQ,[x,y])
    6     sage: I=Ideal(x^2 - 1/2*x - 1/4, y^3 - 1/2*y^2 - 1/2*y + 1/8)
    7     sage: Q=PR.quotient(I)
    8     sage: a,b=Q.gens()
    9     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]])
    10     sage: %timeit elmt^2
    11     1000 loops, best of 3: 1.17 ms per loop
     4sage: def make_matrix1(R,a,b):
     5....:     return matrix(R, 3, [[-1, 1, 2*a],
     6....:            [-4*a*b - 1, 4*a*b + 4*b^2, 4*a*b + 2*a],
     7....:            [-2*a, 2*a + 2*b, 2*a]])
     8sage: PR.<x,y> = PolynomialRing(QQ)
     9sage: I = Ideal(x^2 - 1/2*x - 1/4, y^3 - 1/2*y^2 - 1/2*y + 1/8)
     10sage: Q = PR.quotient(I)
     11sage: elmt = make_matrix1(Q, x, y)
     12sage: %timeit elmt^2
     131000 loops, best of 3: 1.17 ms per loop
    1214
    13     sage: UCF.<E>=UniversalCyclotomicField()
    14     sage: ae=(E(10)+~E(10))/2  #same value as a
    15     sage: be=(E(14)+~E(14))/2  #same value as b
    16     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]])
    17     sage: %timeit m^2
    18     100 loops, best of 3: 8.13 ms per loop
     15sage: UCF.<E> = UniversalCyclotomicField()
     16sage: ae = (E(10)+~E(10))/2  #same value as a
     17sage: be = (E(14)+~E(14))/2  #same value as b
     18sage: m = make_matrix1(UCF, ae, be)
     19sage: %timeit m^2
     20100 loops, best of 3: 8.13 ms per loop
    1921
    20     sage: CF.<F>=CyclotomicField(2*5*7)
    21     sage: af=(F^7+~F^7)/2 #same value as a
    22     sage: bf=(F^5+~F^5)/2 #same value as b
    23     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]])
    24     sage: %timeit m2^2
    25     100 loops, best of 3: 4.99 ms per loop
     22sage: CF.<F> = CyclotomicField(2*5*7)
     23sage: af = (F^7+~F^7)/2 #same value as a
     24sage: bf = (F^5+~F^5)/2 #same value as b
     25sage: m2 = make_matrix1(CF, af, bf)
     26sage: %timeit m2^2
     27100 loops, best of 3: 4.99 ms per loop
    2628}}}
    2729
    … …  
    2931
    3032Here is a univariate example.
     33{{{
     34sage: def make_matrix2(R, a):
     35....:     return matrix(R, 3, [[-2*a, 1, 6*a+2],
     36....:               [-2*a, 2*a, 4*a+1],
     37....:               [0, 0, 1]])
     38sage: PR.<x> = PolynomialRing(QQ)
     39sage: I = Ideal(x^2 - 1/2*x - 1/4)
     40sage: Q = PR.quotient(I)
     41sage: elmt_uni = make_matrix2(Q, x)
     42sage: %timeit elmt_uni*elmt_uni
     431000 loops, best of 3: 1.46 ms per loop
    3144
    32 {{{
    33     sage: PR=PolynomialRing(QQ,[x])
    34     sage: I=Ideal(x^2 - 1/2*x - 1/4)
    35     sage: Q=PR.quotient(I)
    36     sage: elmt_uni=matrix(Q,[[-2*x, 1, 6*x + 2],[-2*x, 2*x, 4*x + 1],[0,0,1]])
    37     sage: %timeit elmt_uni*elmt_uni
    38     1000 loops, best of 3: 1.46 ms per loop
    39 
    40     sage: CF.<F>=CyclotomicField(2*5)
    41     sage: f5=(F+~F)/2
    42     sage: m=matrix(CF,[[-2*f5, 1, 6*f5 + 2],[-2*f5, 2*f5, 4*f5 + 1],[0,0,1]])
    43     sage: type(m)
    44     <type 'sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense'>
    45     sage: m.parent()
    46     Full MatrixSpace of 3 by 3 dense matrices over Cyclotomic Field of order 10 and degree 4
    47     sage: %timeit m*m
    48     100 loops, best of 3: 1.98 ms per loop
     45sage: CF.<F> = CyclotomicField(2*5)
     46sage: f5 = (F+~F)/2
     47sage: m = make_matrix2(CF, f5)
     48sage: type(m)
     49<type 'sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense'>
     50sage: m.parent()
     51Full MatrixSpace of 3 by 3 dense matrices over
     52Cyclotomic Field of order 10 and degree 4
     53sage: %timeit m*m
     54100 loops, best of 3: 1.98 ms per loop
    4955}}}
    5056
    … …  
    5258
    5359{{{
    54     sage: CF.<F>=CyclotomicField(2*5)
    55     sage: f5=(F+~F)/2
    56     sage: m=matrix(CF,[[-2*f5, 1, 6*f5 + 2],[-2*f5, 2*f5, 4*f5 + 1],[0,0,1]])
    57     sage: m.parent()
    58     Full MatrixSpace of 3 by 3 dense matrices over Cyclotomic Field of order 10 and degree 4
    59     sage: type(m)
    60     <type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>
    61     sage: %timeit m*m
    62     1000 loops, best of 3: 251 µs per loop
     60sage: CF.<F> = CyclotomicField(2*5)
     61sage: f5 = (F+~F)/2
     62sage: m = make_matrix2(CF, f5)
     63sage: m.parent()
     64Full MatrixSpace of 3 by 3 dense matrices over
     65Cyclotomic Field of order 10 and degree 4
     66sage: type(m)
     67<type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'>
     68sage: %timeit m*m
     691000 loops, best of 3: 251 µs per loop
    6370}}}
    6471